两两交换链表中的节点

Problem statement

两两交换链表相邻节点，不能修改节点的值

My Solution

思路

先创建一个哑节点，连接链表的起始位置，创建一个指针指向哑节点。先检查是不是空链表，是的话直接返还没有连接哑巴节点的原始链表。随后进入一个while循环，条件是指针节点的下一个节点不是空节点且下一个节点的下一个节点也不是空节点。进入循环后，让指针节点指向下一位的下一位，指针节点的下一位指向指针节点的下一位的下一位的下一位，然后才把指针节点的下一位的下一位指向指针节点的下一位。然后指针向后移动两位。退出循环后，进入一个if判断，如果下一位是空节点，退出循环返还除掉哑节点的链表。如果下一位不是空但是下下一位是空，也返还除掉哑节点的链表

代码

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

ListNode* swapPairs(ListNode* head) {                                         
    ListNode dummy(0);                                                        
    dummy.next = head;                                                        
    ListNode* cur = &dummy;                                                   

    while (cur->next && cur->next->next) {                                    
        ListNode* first = cur->next;                                          
        ListNode* second = cur->next->next;                                   

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

        cur = first;                                                          
    }                                                                         

    return dummy.next;                                                        
}

执行前:
cur

       ↓

dummy → [1] → [2] → [3] → [4]
执行 cur.next = cur.next.next 后:

       cur

       ↓

dummy ───→ [2] → [3] → [4]

       [1] → [2]   ← 节点1没人指着它了，丢了！

执行 cur.next.next = …:
此时 cur.next 是 [2]，cur.next.next 是 [3]
cur.next.next.next.next … 往下数越界了 → None → 崩
正确的顺序是先抓后放——左手抓住 1，右手抓住 2，然后再改指针：
先抓住:

       cur

       ↓

dummy → [1] → [2] → [3] → [4]

       ↑      ↑

     first  second  ← 临时变量握住了

再改线:

first->next = second->next   → 1 指向 3

second->next = first          → 2 指向 1

cur->next = second            → dummy 指向 2

cur = first                   → cur 移到 1（下一组的"前一个"）

结果:

                 cur

                 ↓

dummy → [2] → [1] → [3] → [4]