LeetCode 24 兩兩交換鏈表節點：三種解法全解析

題目描述

給定一個鏈表，每相鄰兩個節點交換位置，返回交換後的鏈表頭結點。要求：

• 只能使用常數級額外空間
• 不能修改節點值，只能改變節點指向

示例： 1→2→3→4 → 2→1→4→3

解法一：交換節點值（簡單但不符合題意）

直接交換相鄰節點的 val。雖然能通過測試，但違反「只能改變節點指向」的限制，僅作參考。

ListNode* swapPairs(ListNode* head) {
    ListNode *p1 = head, *p2;
    int tmp;
    while (p1) {
        p2 = p1->next;
        if (p2) {
            tmp = p1->val;
            p1->val = p2->val;
            p2->val = tmp;
            p1 = p1->next;
        }
        p1 = p1->next;
    }
    return head;
}

解法二：迭代法修改指針（標準解法）

核心難點：交換 p1 和 p2 後，需確保 p2 的前驅正確指向 p2。引入 tmp 記錄上一組交換後的尾節點（即交換前 p1 的前驅）。

ListNode* swapPairs(ListNode* head) {
    ListNode *p1 = head, *p2, *tmp;
    if (p1 && p1->next) head = head->next;  // 新頭結點
    tmp = head;  // 初始時 tmp 指向新頭結點
    
    while (p1) {
        p2 = p1->next;
        if (p2) {
            p1->next = p2->next;
            p2->next = p1;
            if (tmp != head) tmp->next = p2;  // 連接上一組
            tmp = p1;  // 更新 tmp 為當前組的尾節點
        }
        p1 = p1->next;
    }
    return head;
}

解法三：遞歸法（最優雅）

遞歸思維：只處理「第一組」，剩下的交給遞歸。若鏈表少於兩個節點直接返回；否則將 head->next 作為新頭，遞歸處理 head->next->next，最後串聯。

ListNode* swapPairs(ListNode* head) {
    ListNode* p1;
    if (head && head->next) {
        p1 = head->next;              // 新頭結點
        head->next = swapPairs(head->next->next);  // 遞歸處理剩餘
        p1->next = head;              // 完成交換
        head = p1;
    }
    return head;
}

三種解法對比

面試中推薦掌握 迭代修改指針 與 遞歸 兩種標準解法，理解指針操作的本質與遞歸的分治思想。