# 24. 两两交换链表中的节点

# 题目描述

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

示例 1：

输入：head = [1,2,3,4]
输出：[2,1,4,3]

1
2

示例 2：

输入：head = []
输出：[]

1
2

示例 3：

输入：head = [1]
输出：[1]

1
2

提示：

链表中节点的数目在范围 [0, 100] 内
0 <= Node.val <= 100

# 思路

题目要求交换节点，而不是交换节点里的数值。也就是说，我们真正要做的是改变 next 指针的指向。

如果直接从头结点开始操作，第一个结点交换之后，链表的头结点就变了，还要专门处理返回值。怎么统一这种情况呢？

那么就应该想到虚拟头结点了。

令 dummy->next = head，再让 cur 指向 dummy。这样每轮要交换的两个结点就是：

first = cur->next
second = cur->next->next

但只知道这两个结点还不够。交换之后，原来的第一个结点还要接回后面的链表，所以需要先保存：

ListNode* nextPair = second->next;

接下来怎样修改指针，才不会把链表弄断呢？按下面三步来：

cur->next = second;
second->next = first;
first->next = nextPair;

1
2
3

三步完成后，局部链表就从：

cur -> first -> second -> nextPair

变成了：

cur -> second -> first -> nextPair

此时谁是下一轮待交换结点的前一个结点？

正是交换后的 first，所以令 cur = first，继续处理下一对节点。

循环什么时候结束呢？只有 cur 后面至少还有两个结点时，才能进行交换，因此条件是：

cur->next != nullptr && cur->next->next != nullptr

虚拟头结点统一了头结点的处理，而先保存后继节点、再按顺序修改三条指针，是本题不丢节点的关键。

# 模拟过程

为了把奇数个节点的情况也讲清楚，以 head = [1,2,3,4,5] 为例。

先创建虚拟头结点，令 cur = dummy。本轮要交换节点 1 和节点 2，同时先保存节点 3，保证改变指针后仍能找到后面的链表。

接下来按顺序修改三条指针：cur->next 指向节点 2，节点 2 指向节点 1，节点 1 再指回节点 3。第一对节点交换完成，链表变为 [2,1,3,4,5]。

让 cur 移动到节点 1，下一轮用同样的方法交换节点 3 和节点 4。此时节点 5 后面没有第二个节点，循环结束，节点 5 保持不动，最终结果为 [2,1,4,3,5]。

很多录友容易在写完三步指针操作后，让 cur 只移动一位。注意交换后 first 已经变成这一对节点的尾部，下一轮必须从 first 后面开始检查，所以直接令 cur = first 最清晰。

# 解题代码

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode dummy(0, head); // 虚拟头结点，统一第一对节点的交换
        ListNode* cur = &dummy;

        while (cur->next != nullptr && cur->next->next != nullptr) {
            ListNode* first = cur->next;
            ListNode* second = first->next;
            ListNode* nextPair = second->next; // 先保存后继节点，避免断链

            cur->next = second;
            second->next = first;
            first->next = nextPair;

            cur = first; // first 已成为本轮交换后的尾结点
        }

        return dummy.next;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

# 复杂度分析

时间复杂度：O(n)，每个节点只会被处理一次。

空间复杂度：O(1)，只使用了常数个指针。

# 其他语言

# Python3

class Solution:
    def swapPairs(self, head):
        dummy = ListNode(0, head)
        cur = dummy

        while cur.next and cur.next.next:
            first = cur.next
            second = first.next
            next_pair = second.next

            cur.next = second
            second.next = first
            first.next = next_pair

            cur = first

        return dummy.next

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

# Java

class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode dummy = new ListNode(0, head);
        ListNode cur = dummy;

        while (cur.next != null && cur.next.next != null) {
            ListNode first = cur.next;
            ListNode second = first.next;
            ListNode nextPair = second.next;

            cur.next = second;
            second.next = first;
            first.next = nextPair;

            cur = first;
        }

        return dummy.next;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

# Go

func swapPairs(head *ListNode) *ListNode {
    dummy := &ListNode{Val: 0, Next: head}
    cur := dummy

    for cur.Next != nil && cur.Next.Next != nil {
        first := cur.Next
        second := first.Next
        nextPair := second.Next

        cur.Next = second
        second.Next = first
        first.Next = nextPair

        cur = first
    }

    return dummy.Next
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

# JS

var swapPairs = function(head) {
    const dummy = new ListNode(0, head);
    let cur = dummy;

    while (cur.next !== null && cur.next.next !== null) {
        const first = cur.next;
        const second = first.next;
        const nextPair = second.next;

        cur.next = second;
        second.next = first;
        first.next = nextPair;

        cur = first;
    }

    return dummy.next;
};