双向链表上的冒泡排序不起作用

Question

我最近一直在用python做DSA，这次尝试了双向链表上的冒泡排序算法。

不幸的是，该方法没有给出正确的结果。

请纠正我，告诉我哪里出错了（我尝试了很多但无法理解）。请解释并建议所需的更改。

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None
        self.prev = None


class DoublyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None
        self.next = None
        self.prev = None
        self.count = 0

    def bubble_sort(self):
        if self.head is None:
            return f"Linked list is empty!"
        elif self.head.next is None:
            return self.head
        else:
            left = self.head
            right = self.head.next
            while True:
                flag = 'sorted'
                while True:
                    if right is None:
                        break
                    if left.value > right.value:
                        flag = 'unsorted'
                        if (left == self.head) and (right == self.tail): #only two nodes
                            self.tail = left
                            self.head = right
                        elif left == self.head:                    #edge case of left
                            self.head = right
                        elif right == self.tail:                   #edge case of right
                            self.tail = left
                        temp_right = right.next
                        temp_left = left.prev
                        left.next = temp_right
                        left.prev = right
                        right.next = left
                        right.prev = temp_left
                        right = left.next
                    else:
                        left = left.next
                        right = right.next
                left = self.head
                right = self.head.next
                if flag == 'sorted':
                    return self

请帮忙！

Answer 1

当您交换双向链表中间某处的两个节点时，涉及到 4 个节点，并且您的代码已正确识别它们。

这 4 个节点之间有 6 个链接：第一对之间有 2 个链接，中间对之间有 2 个链接，右侧对之间有 2 个链接。

您的代码仅更新四个链接，因此这不可能是正确的。也就是说，您尚未更新

temp_left.next

和

temp_right.prev

链接。

要解决此问题，请更改交换代码，如下所示：

                temp_right = right.next
                temp_left = left.prev
                left.next = temp_right
                left.prev = right
                right.next = left
                right.prev = temp_left
                ## === start of fix === insert these statements:
                if temp_right:
                    temp_right.prev = left
                if temp_left:
                    temp_left.next = right
                ## === end of fix ===
                right = left.next