如何设置首节点prev指向尾节点next构建循环双向链表解决约瑟夫问题报错

1 你的报错原因判断是否正确？ #

你的判断不准确。本次报错的直接原因是：第一次调用insert_after方法插入第2个节点时，传入的首节点current_node的next属性初始值为None，你把x.next赋值给z后，z就是None，执行z.prev = y时自然会抛出NoneType没有prev属性的错误。

你提到的「首节点prev未设置、循环双向链表首尾未关联」属于后续运行会触发的问题，但不是本次报错的直接诱因。

修复方向：

• 先修正insert_after方法的空指针访问问题
• 所有节点插入完成后手动关联首尾节点，完成双向循环结构的构建
• 同步修正约瑟夫环的计数逻辑、循环终止条件的漏洞

2 完整可运行修复方案 #

修正后的代码如下：

class Student:
    # 初始化节点
    def __init__(self, data):
        self.data = data
        self.next = None
        self.prev = None
        
    def remove(self, n):
        print("Student " +str(n)+ " was removed")
        
class Circle:
    # 初始化双向链表
    def __init__(self):
        self.head = None
        self.tail = None
    # 在x节点后插入新节点           
    def insert_after(self, x, data):          
        y = Student(data)
        z = x.next
        
        y.prev = x
        y.next = z
        x.next = y
        # 仅当z不为空时才修改z的prev属性，避免空指针报错
        if z is not None:
            z.prev = y
        return y
    
    def josephus_solution(self, n, k):
        no_of_active_nodes = n
        # 初始化首节点
        head = Student(1)
        current_node = head
        # 插入剩余n-1个节点，同时记录尾节点
        for i in range(2, n + 1):
            current_node = self.insert_after(current_node, i)
        tail = current_node
        # 首尾关联，构建循环双向链表
        head.prev = tail
        tail.next = head
        # 重置当前节点到首节点，初始化计数器
        current_node = head
        count = 0
        while no_of_active_nodes > 1:
            count += 1
            if count == k:
                current_node.remove(current_node.data)
                # 移除当前节点
                current_node.prev.next = current_node.next
                current_node.next.prev = current_node.prev
                no_of_active_nodes -= 1
                count = 0
            # 移动到下一个节点
            current_node = current_node.next
        print("Student " + str(current_node.data) + " Recieves the scholarship")
        return current_node.data

dllist = Circle()
n = 5 
k = 2 
ans = dllist.josephus_solution(n, k)

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