題目網址：https://leetcode.cn/problems/reverse-nodes-in-k-group/

題意：給一 linked list 的 head, 每 k 個 node 一組進行 reverse, 返回修改後的 linked list。

k 為一正整數, 其中 k ≤ linkedList.size()。如果 node 數不為 k 的倍數, 則讓剩餘的 node 保持原先的順序。

必須實際進行 swap node, 不能只是單純改變 node.val。

進階：設計 $O(1)$ space 的演算法。

Solution：

想法：分成以下步驟

  • 先用 groupPre 指向 group 開頭的前一個 node
  • 取得該 group 的第 k 個 node kth, 也就是 group end
  • reverse 從 group head ~ group end 的 node
    • prev 起始設為 kth->next, 因為 reverse 後 group end 必須連接到剩下的 node
  • reverse 完後, 首先記住 reverse 後的 group end（因為等等要將 groupPre 更新成 group end, 只是在那之前要先讓 groupPre->next 指向新的 group head）
  • 將 groupPre->next 指向 reverse 後的 group head
  • 更新 groupPre 為 reverse 後的 group end
  • 重複以上步驟
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        const auto dummy = new ListNode(0, head);
        ListNode *groupPre = dummy;

        while (true) {
            ListNode *kth = getKth(groupPre, k);

            // 如果 group 的第 k 個為 null, 則代表該 group 不足 k 個, 故直接返回
            if (!kth) {
                break;
			}

            // reverse the group
            ListNode *groupNext = kth->next; // 下一個 group 的 head
            ListNode *prev = groupNext, *curr = groupPre->next;

            while (curr != groupNext) {
                ListNode *nxt = curr->next;
                curr->next = prev;
                prev = curr;
                curr = nxt;
            }

            // 記住 reverse 後的 group end(reverse 前的 group head)
            ListNode *originalHead = groupPre->next;

            // 將 group dummy 指向 reverse 後的 group head(reverse 前的 group end)
            groupPre->next = kth;

            // 更新 group dummy 為 reverse 後的 group end
            groupPre = originalHead;
        }

        return dummy->next;
    }

private:
    ListNode* getKth(ListNode* curr, int k){
        while (curr && k > 0) {
            curr = curr->next;
            --k;
        }
        return curr;
    }
};
  • time：$O(n)$ ➔ 遍歷 linked list
  • space：$O(1)$ ➔ 只需常數空間