0024. 两两交换链表中的节点.md

0024. 两两交换链表中的节点

• 标签：递归、链表
• 难度：中等

题目大意

给定一个链表，按顺序每两个节点交换一下，并返回交换后的链表。要求需要实际进行节点交换，而不是纸改变节点内部的值。

解题思路

遍历链表，并判断当前链表后两位节点是否为空。如果后两个节点不为空，则使用三个指针：curr 指向当前节点，node1 指向下一个节点，node2 指向下面第二个节点。

将 curr 指向 node2，node1 指向 node2 后边的节点，node2 指向 node1。则节点关系由 curr → node1 → node2 变为了 curr → node2 → node1。

依次类推，最终返回头节点。

上述我们并判断的是当前链表后两位节点是否为空，可以在一开始的时候新建一个节点 new_head，作为新的头节点加到链表头部，最终返回结果的时候，直接返回 new_head.next 即可。

代码

class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        new_head = ListNode(0)
        new_head.next = head
        curr = new_head
        while curr.next and curr.next.next:
            node1 = curr.next
            node2 = curr.next.next
            curr.next = node2
            node1.next = node2.next
            node2.next = node1
            curr = node1
        return new_head.next