摘自labuladong演算法小抄，使用go語言重新描述
之前的文章「遞回反轉鏈表的一部分」講了如何遞回地反轉一部分鏈表，有讀者就問如何迭代地反轉鏈表，這篇文章解決的問題也需要反轉鏈表的函式，我們不妨就用迭代方式來解決，
本文要解決「K 個一組反轉鏈表」，不難理解：
這個問題經常在面經中看到，而且 LeetCode 上難度是 Hard，它真的有那么難嗎？
對于基本資料結構的演算法問題其實都不難，只要結合特點一點點拆解分析，一般都沒啥難點，下面我們就來拆解一下這個問題，
一、分析問題
首先，前文學習資料結構的框架思維提到過，鏈表是一種兼具遞回和迭代性質的資料結構，認真思考一下可以發現這個問題具有遞回性質，
什么叫遞回性質？直接上圖理解，比如說我們對這個鏈表呼叫 reverseKGroup(head, 2)，即以 2 個節點為一組反轉鏈表：
如果我設法把前 2 個節點反轉，那么后面的那些節點怎么處理？后面的這些節點也是一條鏈表，而且規模（長度）比原來這條鏈表小，這就叫子問題，
我們可以直接遞回呼叫 reverseKGroup(cur, 2)，因為子問題和原問題的結構完全相同，這就是所謂的遞回性質，
發現了遞回性質，就可以得到大致的演算法流程：
1、先反轉以 head 開頭的 k 個元素，
2、將第 k + 1 個元素作為 head 遞回呼叫 reverseKGroup 函式，
3、將上述兩個程序的結果連接起來，
整體思路就是這樣了，最后一點值得注意的是，遞回函式都有個 base case，對于這個問題是什么呢？
題目說了，如果最后的元素不足 k 個，就保持不變，這就是 base case，待會會在代碼里體現，
二、代碼實作
首先，我們要實作一個 ReverseSingleList 函式反轉一個區間之內的元素，在此之前我們再簡化一下，給定鏈表頭結點，如何反轉整個鏈表？
// 反轉以 a 為頭結點的鏈表 func ReverseSingleList(a *ListNode) *ListNode { var ( pre, cur, nxt *ListNode ) pre = nil cur = a nxt = a for cur != nil { nxt = cur.next // 逐個結點反轉 cur.next = pre // 更新指標位置 pre = cur cur = nxt } // 回傳反轉后的頭結點 return pre }
這次使用迭代思路來實作的，借助影片理解應該很容易，
「反轉以 a 為頭結點的鏈表」其實就是「反轉 a 到 null 之間的結點」，那么如果讓你「反轉 a 到 b 之間的結點」，你會不會？
只要更改函式簽名，并把上面的代碼中 null 改成 b 即可：
/** 反轉區間 [a, b) 的元素，注意是左閉右開 */ func ReverseSingleList(a *ListNode, b *ListNode) *ListNode { var ( pre, cur, nxt *ListNode ) pre = nil cur = a nxt = a //終止的條件改一下就行了 for cur != b { nxt = cur.next // 逐個結點反轉 cur.next = pre // 更新指標位置 pre = cur cur = nxt } // 回傳反轉后的頭結點 return pre }
現在我們迭代實作了反轉部分鏈表的功能，接下來就按照之前的邏輯撰寫 reverseKGroup 函式即可：
func ReverseKGroup(head *ListNode, k int) *ListNode { if head == nil { return nil } // 區間 [a, b) 包含 k 個待反轉元素 var ( a, b *ListNode ) b = head a = head for i := 0; i < k; i++ { // 不足 k 個，不需要反轉，base case if b == nil { return head } b = b.next } // 反轉前 k 個元素 newHead := ReverseSingleList(a, b) // 遞回反轉后續鏈表并連接起來 a.next = ReverseKGroup(b, k) return newHead }
解釋一下 for 回圈之后的幾句代碼，注意 ReverseSingleList函式是反轉區間 [a, b)，所以情形是這樣的：
遞回部分就不展開了，整個函式遞回完成之后就是這個結果，完全符合題意：
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/247971.html
標籤：其他