一篇文章教你搞定遞歸單鏈表反轉(zhuǎn)
關(guān)于單鏈表反轉(zhuǎn)，阿粉以前寫過一篇文章，是用迭代法實現(xiàn)的，還有一種方法是使用遞歸來實現(xiàn)的，阿粉一直沒敢寫，因為害怕講不清楚。但是不能因為害怕講不清楚就不寫了，對不對。
所以這篇文章來使用遞歸來實現(xiàn)一下，并且嘗試將里面的細(xì)節(jié)一一剖出來，不廢話。
首先，咱們要先明確，什么是遞歸。遞歸就是自己調(diào)用自己對吧。比如:有一個函數(shù)為 f(n) = f(n-1) * n ，(注意，我這里是舉例子，這個函數(shù)沒有給出遞歸的結(jié)束條件)給 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：
- /**
- * 單鏈表反轉(zhuǎn)---遞歸實現(xiàn)
- */
- 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);
- // 調(diào)用反轉(zhuǎn)方法
- Node recursiveList = recursiveList(node1);
- System.out.println(recursiveList);
- }
- /**
- *遞歸實現(xiàn)單鏈表反轉(zhuǎn)
- * @param list 為傳入的單鏈表
- */
- public static Node recursiveList(Node list){
- // 如果鏈表為空 或者 鏈表中只有一個節(jié)點,直接返回
- // 也是遞歸結(jié)束的條件
- if (list == null || list.next == null) return list;
- Node recursive = recursiveList(list.next);
- // 將 list.next.next 指針指向當(dāng)前鏈表 list
- list.next.next = list ;
- // 將 list.next 指針指向 null
- list.next = null;
- // 返回反轉(zhuǎn)之后的鏈表 recursive
- return recursive;
- }
- }
經(jīng)過上面的代碼，應(yīng)該能夠看到核心代碼就是，遞歸實現(xiàn)單鏈表反轉(zhuǎn)部分的那 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;
第一行就是一個判斷，條件不滿足，那就往下走，第二行是自己調(diào)用自己，程序又回到第一行，不滿足條件程序向下執(zhí)行，自己調(diào)用自己
就這樣循環(huán)到符合條件為止，那么什么時候符合條件呢?也就是 list == null 或者 list.next == null 時，看一下自己定義的鏈表是 1->2->3->4->5->null ，所以符合條件時，此時的鏈表為 5->null ，符合條件之后，程序繼續(xù)向下執(zhí)行，在執(zhí)行完 Node recursive = recursiveList(list.next); 這行代碼之后，咱們來看一下此時的程序執(zhí)行結(jié)果:
我把上面這個給畫出來(阿粉的畫工不是不好，不要在乎它的美丑~)
接下來程序該執(zhí)行 list.next.next = list 執(zhí)行結(jié)束之后，鏈表大概就是這個樣子:
那是圖，下面是程序斷點調(diào)試程序的結(jié)果，發(fā)現(xiàn)和上面的圖是一樣的:
程序繼續(xù)向下走 list.next = null ，也就是說，將 list 的 next 指針指向 null :
從圖中看到， list 為 4->null ， recursive 為 5->4->null ，咱們來看看程序的結(jié)果，是不是和圖相符:
完全一樣有沒有!
OK ，還記得咱們剛開始的遞歸函數(shù)例子嘛?現(xiàn)在執(zhí)行完畢，開始執(zhí)行下一次，咱們繼續(xù)來看，此時的鏈表是這個樣子的:
接下來程序執(zhí)行的代碼就是四行了:
- Node recursive = recursiveList(list.next);
- list.next.next = list ;
- list.next = null;
- return recursive;
繼續(xù)執(zhí)行程序，咱們來看結(jié)果，將 list.next.next = list 運行結(jié)束時，此時鏈表為:
從圖中能夠看到，鏈表 list 為 3->4->3->4 循環(huán)中， recursive 為 5->4->3->4->3 循環(huán)，咱們看一下程序是不是也是如此(在這里我截了兩個循環(huán)作為示例):
接下來程序執(zhí)行 list.next = null ，執(zhí)行完畢之后，就是將 list 的 next 指針指向 null :
從圖中能夠看出來， list 為 3->null ， recursive 為 5->4->3->null ，上圖看看實際結(jié)果和分析的是否一致:
說明什么?!說明咱們上面的分析是正確的。接下來的程序分析，讀者們就自行研究吧，相信接下來的分析就難不倒咱們聰明的讀者啦~
反轉(zhuǎn)單鏈表的前 N 個節(jié)點
OK ，咱們趁熱打鐵一下，剛剛是通過遞歸實現(xiàn)了整個單鏈表反轉(zhuǎn)，那如果我只是想反轉(zhuǎn)前 N 個節(jié)點呢?
比如單鏈表為 1->2->3->4->5->null ，現(xiàn)在我只想反轉(zhuǎn)前三個節(jié)點，變?yōu)? 3->2->1->4->5->null
有沒有想法?
咱們進行整個單鏈表反轉(zhuǎn)時，可以理解為傳遞了一個參數(shù) n ，這個 n 就是單鏈表的長度，然后遞歸程序不斷調(diào)用自己，然后實現(xiàn)了整個單鏈表反轉(zhuǎn)。那么，如果我想要反轉(zhuǎn)前 N 個節(jié)點，是不是傳遞一個參數(shù) n 來解決就好了?
咱們就直接上代碼了:
- /**
- *反轉(zhuǎn)單鏈表前 n 個節(jié)點
- * @param list 為傳入的單鏈表 , n 為要反轉(zhuǎn)的前 n 個節(jié)點
- */
- public static Node next;
- public static Node reverseListN(Node list,int n){
- if (n == 1) {
- // 要進行反轉(zhuǎn)鏈表時,先將 list 后的節(jié)點數(shù)據(jù)保存到 next 中
- next = list.next;
- return list;
- }
- Node reverse = reverseListN(list.next , n-1);
- list.next.next = list;
- // 將 list.next 的指針指向沒有進行反轉(zhuǎn)的鏈表
- list.next = next ;
- return reverse;
- }
反轉(zhuǎn)單鏈表的一部分
既然反轉(zhuǎn)整個單鏈表實現(xiàn)了，反轉(zhuǎn)前 N 個節(jié)點實現(xiàn)了，那么如果有個需求是反轉(zhuǎn)其中的一部分?jǐn)?shù)據(jù)呢?大概就是這樣，原來的鏈表為 1->2->3->4->5->null ，反轉(zhuǎn)其中的一部分，使反轉(zhuǎn)后的鏈表為 1->4->3->2->5->null
借用反轉(zhuǎn)前 N 個節(jié)點的思路，是不是我傳兩個參數(shù)進來，一個是開始反轉(zhuǎn)的節(jié)點，一個是結(jié)束反轉(zhuǎn)的節(jié)點，然后遞歸操作就可以了?
瞅瞅代碼是怎么寫的:
- /**
- *反轉(zhuǎn)部分單鏈表
- * @param list 為傳入的單鏈表, m 為開始反轉(zhuǎn)的節(jié)點, n 為結(jié)束的反轉(zhuǎn)節(jié)點
- */
- 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;
- }
終于給弄清楚了 最后兩個例子，讀者們可以自行研究，我這里因為篇幅的問題就不進行解析了，如果第一個例子自己能夠剖析清楚，下面兩個也沒啥大問題~
其中實現(xiàn)的思路借鑒了網(wǎng)上，真是太巧妙了，分享給大家。
最后，看到阿粉又是調(diào)試程序又是畫圖來幫助大家理解的份上，點點在看支持一下?
