Swap Nodes in Pairs

24. Swap Nodes in Pairs

分析

创建虚拟头节点
- 为了方便处理头节点的交换，创建一个虚拟头节点 dummy，使其 next 指向链表的头节点
遍历链表并交换节点
- 使用指针 cur 指向当前正在处理的一对节点的前驱节点。
- 检查当前节点 cur->next 和 cur->next->next 是否存在，只有在有足够节点时才进行交换
- 定义两个指针 p 和 q 分别指向待交换的两个节点：
  - 交换后，cur->next 指向第二个节点 q
  - 第一个节点 p->next 指向第三个节点
  - 第二个节点 q->next 指向第一个节点
- 将指针 cur 移动到已交换节点对的末尾，继续处理下一对

时间复杂度

时间复杂度 O(n)，遍历链表一次，其中 n 是链表的长度

空间复杂度

空间复杂度 O(1)

C++代码

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


class Solution
{
public:
    ListNode* swapPairs(ListNode* head)
    {
        // 创建虚拟头节点
        ListNode* dummy = new ListNode(-1);
        dummy->next = head;

        // 遍历链表并交换节点
        for (ListNode* cur = dummy; cur->next && cur->next->next; )
        {
            ListNode *p = cur->next, *q = p->next; // 定义待交换的两个节点
            cur->next = q;                         // 前驱节点指向第二个节点
            p->next = q->next;                     // 第一个节点指向第三个节点
            q->next = p;                           // 第二个节点指向第一个节点
            cur = p;                               // 移动到下一组的前驱节点
        }

        // 返回结果链表
        return dummy->next;
    }
};