LeetCode 24 兩兩交換鏈表節點：迭代法實現

LeetCode 24 兩兩交換鏈表節點：迭代法實現

給定單鏈表，每相鄰兩個節點交換位置，返回新頭節點。要求 O(1) 額外空間，只能修改節點指針，不能修改節點值。

算法思路

使用三個指針 p1, p2, p3 輔助交換：

• p1 指向當前待交換的第一個節點
• p2 指向第二個節點
• p3 指向上一組交換後的尾節點（用於連接新頭）

循環條件：p1 != NULL && p1->next != NULL。每輪交換後，p3 移動到原 p2（現為尾），p1, p2 移動到下一組。

關鍵步驟

1. 保存 p1->next 為 nextPair。
2. p1->next = p2->next; p2->next = p1; 完成交換。
3. 若是第一組（n==0），更新 head = p2；否則 p3->next = p2。
4. p3 = p1; p1 = p2 = nextPair; 進入下一輪。

完整代碼

#include <stdio.h>
#include <stdlib.h>

typedef struct ListNode {
    int val;
    struct ListNode *next;
} *ListNode;

ListNode swapPairs(ListNode head) {
    ListNode *p1, *p2, *p3;
    int n = 0;
    for (p1 = p2 = p3 = head; p1 != NULL && p1->next != NULL; n++) {
        p1 = p1->next;
        p2->next = p1->next;
        p1->next = p2;
        if (n != 0) p3->next = p1;
        else head = p1;
        p3 = p2;
        p1 = p2 = p2->next;
    }
    return head;
}

示例：
輸入 1->2->3->4 → 輸出 2->1->4->3。
時間 O(n)，空間 O(1)。