链表，交换节点

Question

我正在尝试解决成对的交换节点（链表）。我有正确的代码，但我在解释交换步骤时陷入困境。

这是代码：

def swapPairs(head):
    pre = ListNode(0)
    pre.next = head

    while pre.next and pre.next.next:
        a = pre.next
        b = a.next
        pre.next, b.next, a.next = b, a, b.next
        pre = a

    return pre.next

例如，如果我的链表是1->2->3->4。最初a指向1，b指向2。在交换步骤中：如何不丢失2之后的链表？因为在我们实际执行 a.next = b.next 之前 b.next 会指向 a？

Answer 1

您必须保留下一对的起始节点以及到目前为止反转的列表的最后一个节点。我不使用Python编码，所以我可以提供一种算法来实现你正在寻找的东西。 您可以检查以下

1. newHead=null
2. previousNode=null
3. while head is not null : // While loop start
      curr = head.next;
      if curr is not null:  // If block
         next= curr.next
         curr.next=head
         head.next=null
      else:
         next=head
                         //If-else block ends here
      
      if prevNode is not null:  // Another if block
         prevNode.next=curr
                                // If block ends here

      prevNode=head
    
      if newNode is null :  // another if block
         newNode=curr
                          // if block ends here
    
      head=next
                        // while loop ends here

4. return newHead         // return head of reversedList

Answer 2

您专注于交换步骤是正确的，因为乍一看这可能很棘手。让我来给你分解一下吧。

您的关键代码行是：

pre.next, b.next, a.next = b, a, b.next 让我们一步一步来看看发生了什么：

初始设置：

a 指向第一个节点（在您的示例中为 1）。 b 指向第二个节点 (2)。 交换之前，链表如下所示：

前 -> 1 (a) -> 2 (b) -> 3 -> 4 交换过程：线路：

pre.next, b.next, a.next = b, a, b.next 同时做三件事：

pre.next = b：这使得 pre 指向 b，所以现在 b 是该对中的第一个节点：

前 -> 2 (b) -> 1 (a) -> 3 -> 4 b.next = a：这使得 b（节点 2）指向 a（节点 1），有效地交换了该对：

前 -> 2 (b) -> 1 (a) -> 3 -> 4 a.next = b.next：最后，这确保 a（节点 1）现在指向 b.next 最初指向的内容（即节点 3），保持与列表其余部分的连接：

前 -> 2 (b) -> 1 (a) -> 3 -> 4 这确保了交换节点 (3 -> 4) 之后的列表部分被保留。

最终结构： 交换后，链表如下所示：

前 -> 2 (b) -> 1 (a) -> 3 -> 4 然后循环将继续处理下一对（如果有）。

为什么有效： 在Python中，元组赋值是同时发生的，因此指针会立即更新，而不会丢失中间值。如果您按顺序更新它们，则可能会在此过程中丢失部分列表。然而，Python 的元组解包使所有内容保持正确连接。