LeetCode #25 Reverse Nodes in k-Group

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 nodes, only nodes itself may be changed.

Only constant memory is allowed.

For example,
Given this linked list: 1->2->3->4->5

For k = 2, you should return: 2->1->4->3->5

For k = 3, you should return: 3->2->1->4->5

這是操作 singly-linked list 的經典問題，對於不常使用的自己來說，一開始實在是有點頭大，尤其是光是 reserve linked-list 便思考很久，但想明白加上實作數多個版本後，原來概念是很簡單的。

分析

根據題意，劃出以下的輸出示意圖，由 linked list 的第一個元素 head node 開始計算，每 k 個 nodes 分成一組進行順序反轉 (reverse)，其餘 nodes 不改變其順序：

這題有條件限制，不能在額外配置記憶體陣列來使用，因此得思考不用暫存空間的解法，其演算法的空間複雜度必須為 O(1)。

從題目得知，演算法的關鍵在於反轉 linked list 的演算法，假設給予 first node 以及 last node 的條件限制，限制在這區間的 nodes 進行順序反轉，畫成圖會是下面的示意圖：

不過要注意的是，原先指向 first 的 node (node 0)，需要調整指向到 last，否則會有資料遺失的問題。

有該反轉函數後，以 k 個 nodes 分為一組進行順序反轉便相當容易，從 head node 開始，往後列舉到第 k 個 node，取得分組的 begin 以及 end node，進行順序反轉，持續到無法再分組為止。

唯一特別的是，建立一個 dummy node 來記錄 linked list 的 head node，如此做可以不必寫例外，讓程式碼更簡潔。

解法

使用 Go：

// 最後的版本
/**
* Definition for singly-linked list.
* type ListNode struct {
*     Val int
*     Next *ListNode
* }
*/
func reverse(first, last *ListNode) *ListNode {
   previous := last.Next
   end := last.Next
   for current := first; current != end; {
      next := current.Next
      current.Next = previous
      previous, current = current, next
   }
   return last // head after reversed
}

func findNthNode(itr *ListNode, n int) *ListNode {
   for i := 1; i < n; i++ {
      itr = itr.Next
   }
   return itr
}

func reverseKGroup(head *ListNode, k int) *ListNode {
   if head == nil || k == 1 {
      return head
   }
   c := 0
   for itr := head; itr != nil; itr = itr.Next {
      c++
   }
   dummy := &ListNode{Next: head}
   itr := dummy
   for c >= k {
      begin := itr.Next
      end := findNthNode(begin, k)
      itr.Next = reverse(begin, end)
      itr = begin  // begin will be last after reverse...
      c -= k
   }
   return dummy.Next
}