• Problem Link: [↗]
• Difficulty: 🔴 Hard
• Problem description:

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list. k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes, in the end, should remain as it is. You may not alter the values in the list’s nodes, only nodes themselves may be changed.

1. Example 1:

   Input: head = [1,2,3,4,5], k = 2
   Output: [2,1,4,3,5]

2. Example 2:

   Input: head = [1,2,3,4,5], k = 3
   Output: [3,2,1,4,5]

3. Example 3:

   Input: head = [1,2,3,4,5], k = 1
   Output: [1,2,3,4,5]

思路

用兩個指標（p1, p2）表示要反轉的區間（類似 sliding window 的感覺）。每反轉好一個區間就將兩個指標往前進 k 步，直到 p2 碰到 nullptr。

First version

ListNode* reverseKGroup(ListNode* head, int k) {
  ListNode* newhead = nullptr;
  ListNode* p1 = head, *p2 = p1, *p0 = nullptr;
  for(int i = 0; p2 && i < k-1; ++i){
    p2 = p2->next;
  }
  while(p2){
    reverseList(p1, p2);
    swap(p1, p2);
    if(p0) p0->next = p1;
    else newhead = p1;
    p0 = p2;
    for(int i = 0; p2 && i < k; ++i){
      p1 = p1->next;
      p2 = p2->next;
    }
  }
  return newhead;
}
ListNode* reverseList( ListNode* a, ListNode* b){
  ListNode* pre = b->next,
          * now = a,
          * nxt= a->next;
  while(now && pre != b){
    now->next = pre;
    pre = now;
    now = nxt;
    if(nxt) nxt = nxt->next;
  }
  return pre;
}

這個版本雖然有過，但有幾點問題：

1. 為了維持 p1 在 p2 前面，多用了一個不必要的 swap。
2. 既然每次 p1 都要給別人（第一次給 newhead，之後都給 p0），有沒有更簡潔的寫法？
3. 為了反轉閉區間 [a,b] 用了修改的反轉函式，比一般的還要多跑一次，以確保最後一個節點 b 有轉到。這樣在在理解上比較不直觀。
   • 使用閉區間表示是希望 p2 == nullptr 只表示最後一段長度不夠的情形（不然必須要再檢查 index i，不管在迴圈外或迴圈內檢查都感覺有點雜亂）。
4. 有很多「將指標往後移動 k 個」的操作，根據 DRY 的原則，應該拉出來做成函式。

Modified version

ListNode* reverseKGroup(ListNode* head, int k) {
    if (k == 1) return head;
    ListNode*  p1 = head;
    ListNode*  p2 = next(head, k-1);
    ListNode*  newhead = nullptr;
    ListNode** prelink = &newhead;
    while(p2){
        // 1st iter  : Set newhead to p2
        // otherwise : Connect the previous section with this one
        *prelink = reverseRange(p1, p2);
        // now p1 points to the new tail, and p2 points to the new head
        // Points to the `next` of the tail of this section
        prelink  = &p1->next;
        // Next section starts from the next of the tail
        p1       = p1->next;
        // Next section ends at the k-1th node after its head
        p2       = next(p1, k-1);
    }
    return newhead;
}

// Reverse a closed interval [a, b]
ListNode* reverseRange(ListNode* a, ListNode* b){
    // Points `pre` to the node that `now` should connet to
    ListNode* pre = b->next,
            * now = a;
    for(ListNode* nxt = now->next; nxt != b->next; nxt = nxt->next){
        now->next = pre;
        pre = exchange(now, nxt);
    }
    now->next = pre;
    return now;
}

// Get the nth next node, stop if null
ListNode* next(ListNode* n, size_t k) {
    for(size_t i = 0; n && i < k; ++i)
        n = n->next;
    return n;
}

修正了之前提到的問題：

1. 將「k 為一」的狀況直接回傳，避免不必要的計算。
2. 利用雙重指標來解決 p0 的問題，此處 prelink 可以理解為「上一段尾端的接口」。最一開始指向 newhead（算是長度為 0 的 linked list），因此在第一次迴圈會把第一段的頭「接到」 newhead 後；往後的迴圈會自動將上一段與這一段接好，不會動到 newhead。
3. 利用「反轉後 pre 會接在 head」後面的性質，將 b->next 紀錄到 pre 。再將停止條件設為 nxt == b->next，用一般的反轉演算法來解。另外因為不會出現 b 為 nullptr 的狀況，因此省略檢查。
4. 把「將指標往後移動 k 個」獨立出來，讓程式架構更清爽。

Recursive version

偷看別人的解答後發現可以用遞迴來寫，來試試看。

ListNode* reverseKGroup(ListNode* head, int k) {
  if(k == 1) return head;
  if(ListNode* tail = next(head, k-1); !tail){
      return head;
  }else{
      reverseRange(head, tail);
      // now `tail` points to the new head
      //     `head` points to the new tail
      head->next = reverseKGroup(head->next, k);
      return tail;
  }
}

遞迴真的能寫得很簡潔啊，只需要一個變數…

想法

一開始是在每月挑戰寫到這題，寫完之後才發現是 hard 的題目。過去都感覺 hard 難到爆炸，這次自己解了一題後就比較有信心了（雖然這題應該算 hard 中的 easy）。

另外以 Node 為元素的 linked list 有型別 L[Node] ，這個型別可以視為以 nullptr 為單位元素的單群（Monoid）；也對應到 Haskell 裡面的 List 。如此一來「將 『指向 nullptr 的指標』 視為空 linked list」的概念就比較具體了。

Full Solution