开拓者建村挑战：我的链表实现为何输出错误？

挑战描述 #

给定若干开拓者（pioneer），他们可以建造村落（village）。这些村落建在一条直线上，从左到右有固定顺序。初始时没有村落。开拓者建造村落后，该村落永远归其所有，且开拓者会居住在该村落，直到迁居至其他村落。

输入定义一系列操作，每个操作指定一位开拓者（以0-based索引标识）及其动作（action）：

• 动作build：指定开拓者在当前居住位置的紧邻右侧建造新村落；若开拓者尚无居所，则新村落成为最左侧村落。若当前居所右侧已有村落，则新村落插入到当前居所与右侧村落之间。操作完成后，新村落成为该开拓者的居所。
• 动作move：指定开拓者将居所迁至下一个村落；若没有下一个村落，则留在原地。

程序需输出所有建成村落的所有者，按从左到右的顺序排列，需考虑输入中的所有操作。

输入格式 #

第一行是两个空格分隔的数字：开拓者数量和操作数量
每个操作占一行，包含两部分，空格分隔：开拓者编号和动作类型（build或move）

输出格式 #

输出第一行是村落数量
每个村落按顺序单独一行，输出对应村落的开拓者索引

示例 #

输入 #

2 4
0 build
1 build
1 move
1 build

预期输出 #

3
1
0
1

示例说明：两位开拓者（0和1）。开拓者0创建第一个村落，开拓者1创建一个村落插入到该村落左侧，然后迁居至另一个村落，最后在该村落右侧创建新村落。

我的实现思路与代码 #

我使用链表（linked list）数据结构来存储村落，代码如下：

class Village:
    def __init__(self, owner=None):
        self.owner = owner
        self.next = None

class Pioneer:
    def __init__(self, position):
        self.position = None

    def main():
       k, n = map(int, input().split())
    
       pioneers = [Pioneer(i) for i in range(k)]

       starting_village = Village()
       current_village = starting_village

       villages = [starting_village]

        for i in range(n):
            pioneer, action = map(str, input().split())

            if action == "move":
                if current_village.next is not None:
                    current_village = current_village.next
                pioneers[int(pioneer)].position = current_village
    
            elif action == "build":
                new_village = Village(owner=pioneer)
                if current_village.next is not None:
                    new_village.next = current_village.next
                current_village.next = new_village
                pioneers[int(pioneer)].position = new_village
                villages.append(new_village)

        m = len(villages) - 1
        print(m)

        current_village = starting_village.next
        while current_village is not None:
            print(current_village.owner)
            current_village = current_village.next

    if __name__ == "__main__":
        main()

问题 #

对于示例输入，我的代码输出：

3
1
1
0

这明显不符合预期输出，请问我的错误是什么？

错误分析与修正 #

核心错误点 #

1. 误用全局current_village变量：所有操作都基于全局的current_village，而非当前操作的开拓者自己的position。这完全违背了需求——每个开拓者有独立的居所，操作应该针对该开拓者的当前位置。
2. 未处理开拓者无居所的build场景：当开拓者position为None时，需要新建最左侧村落（插入链表头部），但代码直接在全局starting_village右侧添加，导致位置错误。
3. move操作逻辑错误：同样操作全局变量，而非对应开拓者的position，导致迁居行为完全不符合预期。

修正后的代码 #

class Village:
    def __init__(self, owner=None):
        self.owner = owner
        self.next = None

class Pioneer:
    def __init__(self):
        self.position = None  # 初始无居所

def main():
    k, n = map(int, input().split())
    pioneers = [Pioneer() for _ in range(k)]
    head = None  # 链表头部，记录最左侧村落

    for _ in range(n):
        parts = input().split()
        pioneer_idx = int(parts[0])
        action = parts[1]
        p = pioneers[pioneer_idx]

        if action == "move":
            # 只有当前有居所且下一个村落实在时，才移动
            if p.position is not None and p.position.next is not None:
                p.position = p.position.next

        elif action == "build":
            new_village = Village(owner=pioneer_idx)
            if p.position is None:
                # 无居所，新建最左侧村落
                new_village.next = head
                head = new_village
                p.position = new_village
            else:
                # 在当前居所右侧插入新村落
                new_village.next = p.position.next
                p.position.next = new_village
                p.position = new_village

    # 统计村落数量并输出
    count = 0
    current = head
    temp = []
    while current is not None:
        temp.append(current.owner)
        count += 1
        current = current.next
    
    print(count)
    for owner in temp:
        print(owner)

if __name__ == "__main__":
    main()

修正说明 #

• 移除全局current_village，所有操作基于当前开拓者的position属性。
• 新增head变量维护链表头部，处理无居所开拓者的build操作（插入头部）。
• move操作仅修改当前开拓者的position，不再影响全局状态。
• 村落owner存储为整数类型，输出更规范。

内容的提问来源于stack exchange，提问作者mouin