如何修复双向循环链表冒泡排序中swap函数的断言错误？

问题根源 #

触发AssertionError: 双向指针关系破坏的核心原因是swap函数未正确维护双向循环链表的所有指针关联——仅修改了部分节点的next或prev，导致某个节点的next.prev不等于自身，破坏了双向链表的结构完整性。

正确的swap实现（MyList类方法） #

def swap(self, a, b):
    # 同一节点无需交换
    if a is b:
        return
    
    # 预存所有关联节点的指针
    a_prev = a.prev
    a_next = a.next
    b_prev = b.prev
    b_next = b.next

    # 情况1：a和b相邻（a在b的前一个位置）
    if a_next is b:
        a_prev.next = b
        b.prev = a_prev
        b_next.prev = a
        a.next = b_next
        b.next = a
        a.prev = b
    # 情况2：b在a的前一个位置（相邻的反向情况）
    elif b_next is a:
        self.swap(b, a)
        return
    # 情况3：a和b不相邻
    else:
        # 将a放到b原位置
        a_prev.next = b
        b_next.prev = a
        b.prev = a_prev
        a.next = b_next
        # 将b放到a原位置
        b_prev.next = a
        a_next.prev = b
        b.next = a_next
        a.prev = b_prev

    # 若head指向被交换节点，同步更新head
    if self.head is a:
        self.head = b
    elif self.head is b:
        self.head = a

swap逻辑说明 #

1. 先处理同一节点的无效交换场景，避免无意义操作。
2. 预存所有关联节点的指针，防止后续修改后丢失引用。
3. 分相邻/不相邻两种核心场景处理：
   • 相邻节点需要额外维护两者之间的直接关联，避免指针链断裂。
   • 不相邻节点则分别将两个节点插入对方的原位置，确保所有前驱/后继指针正确关联。
4. 最后同步更新head指针，避免排序后链表头部指向错误节点。

适配的冒泡排序实现 #

def bubble_sort(self):
    # 空链表或单节点链表无需排序
    if not self.head or self.head.next is self.head:
        return

    swapped = True
    # 记录最后一次交换的位置，减少无效遍历
    last_swapped = self.head

    while swapped:
        swapped = False
        current = self.head
        # 遍历到上一轮最后交换的位置，后续元素已排序完成
        while current.next is not last_swapped:
            if current.key > current.next.key:
                self.swap(current, current.next)
                swapped = True
                # 更新最后交换位置，缩小下一轮遍历范围
                last_swapped = current
            else:
                current = current.next
        # 若最后交换位置回到head，说明全链表已排序
        if last_swapped is self.head:
            break

冒泡排序逻辑说明 #

• 用last_swapped标记已排序的边界，避免循环链表中无限遍历。
• 每次交换后更新边界，减少后续不必要的比较，提升效率。
• 仅当本轮无交换发生时终止循环，确保排序完成。

测试验证 #

# 初始化链表
ml = MyList()
for key in [3, 1, 4, 2]:
    ml.insert(key)

print("排序前:", ml.tolist())  # 输出: [2, 4, 1, 3]
ml.bubble_sort()
print("排序后:", ml.tolist())  # 输出: [1, 2, 3, 4]

运行后不会触发AssertionError，且排序结果正确。

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