交换双向链表中的两个节点

Question

我有以下代码用于尝试交换 dll 中的 2 个节点：

def swap_nodes(self, index_1, index_2):
        node_1 = self[index_1]
        node_2 = self[index_2]

        node_2.next.prev = node_1
        node_2.prev.next = node_1
        node_1.prev.next = node_2
        node_1.next.prev = node_2

        temp_node_1 = node_1
        node_1.next = node_2.next
        node_1.prev = node_2.prev
        node_2.next = temp_node_1.next
        node_2.prev = temp_node_1.prev

def __getitem__(self, index):
        c = 0
        for node in self:
            if c == index:
                return node
            c += 1
        if c < index + 1:
            raise IndexError

运行它在这个 dll 上：

1 <-> 3 <-> 4 <-> 6 <-> 7 <-> 10

制作这个：

1 <-> 3 <-> 7 <-> 10

我怎样才能让它工作？（假设它不包括 head/last 节点）

Answer 1

我认为你这里的问题是你没有复制 temp_node_1 所以接下来的两行实际上也修改 temp_node_1，所以当您尝试使用节点的“旧版本”时，它实际上使用更新的 node_2.

尝试单独保存旧版本的字段，因此：

# Instead of this
temp_node_1 = node_1
# Do this
temp_next = node_1.next
temp_prev = node_1.prev
# And then use these pointers accordingly:
node_1.next = node_2.next               # No change
node_1.prev = node_2.prev               # No change
node_2.next = temp_next
node_2.prev = temp_prev

交换双向链表中的两个节点

Swap two nodes in a doubly linked list

python

linked-list

nodes

doubly-linked-list