利用遞歸方法實現鏈表反轉、前N個節點反轉以及中間部分節點反轉

一、反轉整個鏈表

問題:定義一個函數,輸入一個鏈表的頭節點,反轉該鏈表並輸出反轉後鏈表的頭節點。

示例:

輸入: 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為起點的鏈表反轉,並返回反轉之後的頭節點。

明白了函數的定義後,在來看這個問題。比如我們想反轉這個鏈表

截屏2020-09-05 21.06.50

那麼輸入reverse(head)後,會在ListNode ret = reverse(head.next);進行遞歸

不要跳進遞歸!(你的腦袋能壓幾個棧呀?)

根據reverse函數的定義,函數調用後會返回反轉之後的頭節點,我們用變量ret接收

截屏2020-09-05 21.14.18現在再來看一下代碼

head.next.next = head;

截屏2020-09-05 21.16.19

接下來:

head.next = null;
return ret;

截屏2020-09-05 21.18.16

再跳出這層遞歸就會得到:

截屏2020-09-05 21.19.41

神不神奇,這樣整個鏈表就反轉過來了!

遞歸代碼就是這麼簡潔優雅,但要注意兩個問題:

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!