一、反轉整個鏈表
問題：定義一個函式，輸入一個鏈表的頭節點，反轉該鏈表并輸出反轉后鏈表的頭節點，
示例:
輸入: 1->2->3->4->5->NULL
輸出: 5->4->3->2->1->NULL
//單鏈表的實作結構
public class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x;}
}
反轉鏈表利用迭代不難實作，如果使用遞回則有些許難度，
首先來看原始碼實作：
ListNode reverse(ListNode head) {
if(head == null || head.next == null)
return head;
ListNode ret = reverse(head.next);
head.next.next = head;
head.next = null;
return ret;
}
是否看起來不知所云，而又被這如此簡潔的代碼所震撼？讓我們一起探索一下其中的奧秘，
對于遞回演算法，最重要的是明確遞回函式的定義，
我們的reverse函式的定義如下：
輸入一個節點head,將以head為起點的鏈表反轉，并回傳反轉之后的頭節點，
明白了函式的定義后，在來看這個問題，比如我們想反轉這個鏈表
那么輸入reverse（head）后，會在ListNode ret = reverse(head.next);進行遞回
不要跳進遞回！（你的腦袋能壓幾個堆疊呀？）
根據reverse函式的定義，函式呼叫后會回傳反轉之后的頭節點，我們用變數ret接收
現在再來看一下代碼
head.next.next = head;
接下來：
head.next = null;
return ret;
再跳出這層遞回就會得到：
神不神奇，這樣整個鏈表就反轉過來了！
遞回代碼就是這么簡潔優雅，但要注意兩個問題：
1、遞回函式要有base case，不然就會一直遞回，導致堆疊溢位
if (head == null || head.next == null) return head;
即鏈表為慷訓只有一個節點，直接回傳
2、當鏈表遞回反轉后，新的頭節點為ret,而head變成了最后一個節點，應該令鏈表的某尾指向null
head.next = null;
理解這兩個問題之后，我們可以進一步深入研究鏈表反轉的問題，接下來的問題其實均為在這個演算法上的擴展，
二、反轉鏈表前N個節點
接下來我們來看這個問題：
問題：反轉鏈表前N個節點，并回傳鏈表頭節點
說明：1 <= N <= 鏈表長度
示例:
輸入: 1->2->3->4->5->NULL, n = 4
輸出: 4->3->2->1->5->NULL
解決思路和反轉整個鏈表差不多，只需稍加修改
ListNode successor = null; // 后驅節點（第 n + 1 個節點）
ListNdoe reverseN(ListNode head, int n) {
if (n == 1) {
successor = head.next;
return head;
}
// 以 head.next 為起點，需要反轉前 n - 1 個節點
ListNode ret = reverseN(head.next, n - 1);
head.next.next = head;
head.next = successor; // 將反轉后的 head 與后面節點連接
return ret;
}
具體區別：
1、base case 變為n == 1, 同時需要記錄后驅節點，
2、之前把head.next 設定為null,因為整個鏈表反轉后，head變為最后一個節點，
現在head節點在遞回反轉后不一定為最后一個節點，故應記錄后驅successor(第 n + 1 個節點), 反轉之后將head連接上，
OK，如果這個函式你也能看懂，就離實作反轉一部分鏈表不遠了，
三、反轉鏈表的一部分
現在我們開始解決這個問題，給一個索引區間[m, n]（索引從1開始），僅僅反轉區間中的鏈表元素，
說明：1 <= m <= n <= 鏈表長度
示例：
輸入: 1->2->3->4->5->NULL, m = 2, n = 4
輸出: 1->4->3->2->5->NULL
猛一看很難想到思路，
試想一下，如果m == 1,就相當于反轉鏈表的前 n 元素嘛，也就是我們剛才實作的功能：
ListNode reverseBetween(ListNode head, int m, int n) {
//base case
if (m == 1) {
return reverseN(head, n); // 相當于反轉前 n 個元素
}
// ...
}
那如果m != 1 該怎么辦？
如果把head的索引視為1，那么我們是想從第m個元素開始反轉；
如果把head.next的索引視為1，那么我們是想從第m - 1 個元素開始反轉；
如果把head.next.next的索引視為1，那么我們是想從第m - 2 個元素開始反轉；
......
區別于迭代思想，這就是遞回的思想，所以我們可以完成代碼：
ListNode reverseBetween(ListNode head, int m, int n) {
// base case
if (m == 1) {
return reverseN(head, n);
}
// 遞回前進到觸發 base case （m == 1）
head.next = reverseBetween(head.next, m - 1, n - 1);
return head;
}
至此，我們終于干掉了大BOSS！
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/646.html
標籤：其他