一篇文章教你搞定遞歸單鏈表反轉
關于單鏈表反轉，阿粉以前寫過一篇文章，是用迭代法實現的，還有一種方法是使用遞歸來實現的，阿粉一直沒敢寫，因為害怕講不清楚。但是不能因為害怕講不清楚就不寫了，對不對。
所以這篇文章來使用遞歸來實現一下，并且嘗試將里面的細節一一剖出來，不廢話。
首先，咱們要先明確，什么是遞歸。遞歸就是自己調用自己對吧。比如:有一個函數為 f(n) = f(n-1) * n ，(注意，我這里是舉例子，這個函數沒有給出遞歸的結束條件)給 n 賦值為 5 ， 則:
- --> f(5)
- --> 5 * f(4)
- --> 5 * ( 4 * f(3))
- --> 5 * ( 4 * (3 * f(2)))
- --> 5 * ( 4 * ( 3 * ( 2 * f (1))))
- --> 5 * ( 4 * ( 3 * ( 2 * 1)))
- --> 5 * ( 4 * ( 3 * 2))
- --> 5 * ( 4 * 6 )
- --> 5 * 24
- --> 120
在看完例子之后，咱們接下來不 BB ，直接 show code：
- /**
- * 單鏈表反轉---遞歸實現
- */
- public class ReverseSingleList {
- public static class Node{
- private int data;
- private Node next;
- public Node( int data , Node next){
- this.data = data;
- this.next = next;
- }
- public int getData(){return data;}
- }
- public static void main(String[] args){
- // 初始化單鏈表
- Node node5 = new Node(5,null);
- Node node4 = new Node(4,node5);
- Node node3 = new Node(3,node4);
- Node node2 = new Node(2,node3);
- Node node1 = new Node(1,node2);
- // 調用反轉方法
- Node recursiveList = recursiveList(node1);
- System.out.println(recursiveList);
- }
- /**
- *遞歸實現單鏈表反轉
- * @param list 為傳入的單鏈表
- */
- public static Node recursiveList(Node list){
- // 如果鏈表為空 或者 鏈表中只有一個節點,直接返回
- // 也是遞歸結束的條件
- if (list == null || list.next == null) return list;
- Node recursive = recursiveList(list.next);
- // 將 list.next.next 指針指向當前鏈表 list
- list.next.next = list ;
- // 將 list.next 指針指向 null
- list.next = null;
- // 返回反轉之后的鏈表 recursive
- return recursive;
- }
- }
經過上面的代碼，應該能夠看到核心代碼就是，遞歸實現單鏈表反轉部分的那 5 行代碼，別小看了這 5 行代碼，想要真正弄清楚還真的挺不容易的。
我把這 5 行代碼貼在這里，咱們一行行分析，爭取看完這篇博客就能懂~(注釋我就去掉了，咱們專心看這幾行核心代碼)
- if (list == null || list.next == null) return list;
- Node recursive = recursiveList(list.next);
- list.next.next = list ;
- list.next = null;
- return recursive;
第一行就是一個判斷，條件不滿足，那就往下走，第二行是自己調用自己，程序又回到第一行，不滿足條件程序向下執行，自己調用自己
就這樣循環到符合條件為止，那么什么時候符合條件呢?也就是 list == null 或者 list.next == null 時，看一下自己定義的鏈表是 1->2->3->4->5->null ，所以符合條件時，此時的鏈表為 5->null ，符合條件之后，程序繼續向下執行，在執行完 Node recursive = recursiveList(list.next); 這行代碼之后，咱們來看一下此時的程序執行結果:
我把上面這個給畫出來(阿粉的畫工不是不好，不要在乎它的美丑~)
接下來程序該執行 list.next.next = list 執行結束之后，鏈表大概就是這個樣子:
那是圖，下面是程序斷點調試程序的結果，發現和上面的圖是一樣的:
程序繼續向下走 list.next = null ，也就是說，將 list 的 next 指針指向 null :
從圖中看到， list 為 4->null ， recursive 為 5->4->null ，咱們來看看程序的結果，是不是和圖相符:
完全一樣有沒有!
OK ，還記得咱們剛開始的遞歸函數例子嘛?現在執行完畢，開始執行下一次，咱們繼續來看，此時的鏈表是這個樣子的:
接下來程序執行的代碼就是四行了:
- Node recursive = recursiveList(list.next);
- list.next.next = list ;
- list.next = null;
- return recursive;
繼續執行程序，咱們來看結果，將 list.next.next = list 運行結束時，此時鏈表為:
從圖中能夠看到，鏈表 list 為 3->4->3->4 循環中， recursive 為 5->4->3->4->3 循環，咱們看一下程序是不是也是如此(在這里我截了兩個循環作為示例):
接下來程序執行 list.next = null ，執行完畢之后，就是將 list 的 next 指針指向 null :
從圖中能夠看出來， list 為 3->null ， recursive 為 5->4->3->null ，上圖看看實際結果和分析的是否一致:
說明什么?!說明咱們上面的分析是正確的。接下來的程序分析，讀者們就自行研究吧，相信接下來的分析就難不倒咱們聰明的讀者啦~
反轉單鏈表的前 N 個節點
OK ，咱們趁熱打鐵一下，剛剛是通過遞歸實現了整個單鏈表反轉，那如果我只是想反轉前 N 個節點呢?
比如單鏈表為 1->2->3->4->5->null ，現在我只想反轉前三個節點，變為 3->2->1->4->5->null
有沒有想法?
咱們進行整個單鏈表反轉時，可以理解為傳遞了一個參數 n ，這個 n 就是單鏈表的長度，然后遞歸程序不斷調用自己，然后實現了整個單鏈表反轉。那么，如果我想要反轉前 N 個節點，是不是傳遞一個參數 n 來解決就好了?
咱們就直接上代碼了:
- /**
- *反轉單鏈表前 n 個節點
- * @param list 為傳入的單鏈表 , n 為要反轉的前 n 個節點
- */
- public static Node next;
- public static Node reverseListN(Node list,int n){
- if (n == 1) {
- // 要進行反轉鏈表時,先將 list 后的節點數據保存到 next 中
- next = list.next;
- return list;
- }
- Node reverse = reverseListN(list.next , n-1);
- list.next.next = list;
- // 將 list.next 的指針指向沒有進行反轉的鏈表
- list.next = next ;
- return reverse;
- }
反轉單鏈表的一部分
既然反轉整個單鏈表實現了，反轉前 N 個節點實現了，那么如果有個需求是反轉其中的一部分數據呢?大概就是這樣，原來的鏈表為 1->2->3->4->5->null ，反轉其中的一部分，使反轉后的鏈表為 1->4->3->2->5->null
借用反轉前 N 個節點的思路，是不是我傳兩個參數進來，一個是開始反轉的節點，一個是結束反轉的節點，然后遞歸操作就可以了?
瞅瞅代碼是怎么寫的:
- /**
- *反轉部分單鏈表
- * @param list 為傳入的單鏈表, m 為開始反轉的節點, n 為結束的反轉節點
- */
- public static Node reverseBetween(Node list , int m , int n){
- if (m == 1){
- return reverseListN(list,n);
- }
- list.next = reverseBetween(list.next,m-1,n-1);
- return list;
- }
終于給弄清楚了 最后兩個例子，讀者們可以自行研究，我這里因為篇幅的問題就不進行解析了，如果第一個例子自己能夠剖析清楚，下面兩個也沒啥大問題~
其中實現的思路借鑒了網上，真是太巧妙了，分享給大家。
最后，看到阿粉又是調試程序又是畫圖來幫助大家理解的份上，點點在看支持一下?
