[每日一題]25. Reverse Nodes in k-Group

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

題目解析

這道題的難度是 Hard, 是對我們這一周鍊表練習的一次檢測。

題目的意思是要我們將一個鍊表分成 n / k 個部分，如果 n / k > k 那麼則翻轉。舉了一個例子: k = 2, linked: 1 -> 2 -> 3 -> 4 -> 5

上面的鍊表可以分成 3 個部分: 1 -> 2, 3 -> 4, 5:

翻轉 1 -> 2 得 2 -> 1

翻轉 3 -> 4 得 4 -> 3

因為 5 只有一個節點，不需要翻轉

期望結果 2 -> 1 -> 4 -> 3 -> 5

由上面的分析，我們將這個複雜的問題分成兩個子問題:

鍊表如何分組?

分組的思路很簡單: 用一個數字標記當前節點的位置。

count = 1 while head && count < k do head = head.next count += 1 end

上面的代碼非常容易的獲取鍊表的前 k 個節點，結合遞歸或者循環，就能非常容易的分組了。

鍊表如何反轉?

反轉的思路: 兩個指針: 當前指針 和 前指針 ，通過不斷的操作指針的節點和指針來反轉鍊表。

收錄的部分代碼

@fzy 提交的 Java 代碼: 思路非常清晰，代碼簡潔。

@Gerrold_Gao 提交的 python 代碼: 簡潔，鍊表反轉只有一行代碼

相關issue

https://leetcode.com/problems/swap-nodes-in-pairs

這道題只是中等難度，只是本題的k = 2的一種特殊情況。 @小小鵝 的解決方案特別的好，所以也記錄下來。

鍊表問題的總結

鍊表問題考察最多的是對指針的靈活運用。比如交換鍊表的位置，遞歸，排序等問題，都需要我們熟練的使用指針。有時候畫一張簡單的圖可以簡化我們的思考，幫助我們找到可能的方案。 下面總結的問題和方法都是非常經典的，可以作為學習鍊表的大綱。

鍊表問題可以歸為如下幾種類型:

解題方法有:

指針

環路: 將單向鍊表連接成環

遞歸

二分法

分治算法

Dummy 節點: 簡化對head節點的處理