題目網址：https://leetcode.cn/problems/swap-nodes-in-pairs/

題意：給一 linked list, 兩兩交換相鄰的 node, 並返回交換後 linked list。

注意：必須在不修改 node 值的情況下完成（只能進行 node swap）

Solution：

想法：利用 dummy node, 讓 prev 永遠指向當前 pair 的前一個 node, 分為三步驟

  • 1. 取得下一個 pair 的 head, 和當前 pair 的 tail
  • 2. reverse 當前 pair, 並將 prev 指向當前 pair 的 head(更新前的 tail)
  • 3. 更新 pointers
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode *dummy = new ListNode(0, head);
        ListNode *prev = dummy, *cur = head;

        while (cur && cur->next) {
            // save ptrs
            ListNode *nxtPair = cur->next->next; // 下一個 pair 的 head
            ListNode *second = cur->next; // 當前 pair 的 tail

            // reverse current pairs
            second->next = cur; // second 成為當前 pair 的 head, cur 則成為 tail
            cur->next = nxtPair; // 當前 pair 的 tail 指向下一個 pair
            prev->next = second; // prev 指向當前 pair 的 head

            // update ptrs
            prev = cur; // prev 指向下一個 pair 的前一個 node(當前 pair 的 tail)
            cur = nxtPair; // 移動到下一個 pair
        }

        return dummy->next;
    }
};
  • time：$O(n)$ ➔ 遍歷整個 linked list
  • space：$O(1)$ ➔ 只需常數空間