python - 如何在不交换数据的情况下对双向链表进行冒泡排序（仅传输链接）

Question

我在排序方法中的代码有问题。我需要在不更改任何数据的情况下对双向链表中的节点进行排序，只能在节点的下一个和上一个部分传输（更改节点）。

我试图通过这个例子进行排序：

def sort(self):
        # Check if head is None
        if self.head is None:
            return

        if self.head.next is None:
            return

        # Sort
        change = 1
        while change:
            # Variables
            change = 0
            curr = self.head
            # Sort one iteration
            while curr.next is not None:
                if curr.data < curr.next.data:
                    change = 1

                    temp_curr = curr.prev
                    print(temp_curr)
                    curr.prev = curr.next
                    print(curr.prev)
                    curr.next = curr.next.next
                    print(curr.next)
                    temp_next = curr.next.prev
                    curr.next.prev = temp_curr
                    curr.next.next = temp_next
                curr = curr.next

class ListNode(object):
    def __init__(self, data):
        # store data
        self.data = data
        # store reference (next item)
        self.next = None
        # store reference (previous item)
        self.previous = None


class List(object):
    def __init__(self):
        self.head = None

    def add_list_item(self, item):
        if isinstance(item, ListNode):
            if self.head is None:
                self.head = item
                item.previous = None
                item.next = None
            else:
                curr = self.head
                while curr.next is not None:
                    # Iterate
                    curr = curr.next
                # Add item into tail
                curr.next = item
                item.previous = curr
                item.next = None

    def print_ls(self):
        # Start from head
        current_node = self.head
        # Iterate via the whole list
        while current_node is not None:
            # Print one at one
            print(current_node.data)
            # jump to the linked node
            current_node = current_node.next

    def sort(self):
        # Check if head is None
        if self.head is None:
            return

        if self.head.next is None:
            return

        # Sort
        change = 1
        while change:
            # Variables
            change = 0
            curr = self.head
            # Sort one iteration
            while curr.next is not None:
                if curr.data < curr.next.data:
                    change = 1

                    temp_curr = curr.prev
                    print(temp_curr)
                    curr.prev = curr.next
                    print(curr.prev)
                    curr.next = curr.next.next
                    print(curr.next)
                    temp_next = curr.next.prev
                    curr.next.prev = temp_curr
                    curr.next.next = temp_next
                curr = curr.next

if __name__ == '__main__':
    link_list = List()

    link_list.add_list_item(ListNode(2))
    link_list.add_list_item(ListNode(1))
    link_list.add_list_item(ListNode(3))

    link_list.sort()
    link_list.print_ls()

标签： pythonsortingdoubly-linked-list