您好,登錄后才能下訂單哦!
這篇文章主要講解了“怎么理解Java遞歸單鏈表反轉”,文中的講解內容簡單清晰,易于學習與理解,下面請大家跟著小編的思路慢慢深入,一起來研究和學習“怎么理解Java遞歸單鏈表反轉”吧!
首先,咱們要先明確,什么是遞歸。遞歸就是自己調用自己對吧。比如:有一個函數為 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; }
感謝各位的閱讀,以上就是“怎么理解Java遞歸單鏈表反轉”的內容了,經過本文的學習后,相信大家對怎么理解Java遞歸單鏈表反轉這一問題有了更深刻的體會,具體使用情況還需要大家實踐驗證。這里是億速云,小編將為大家推送更多相關知識點的文章,歡迎關注!
免責聲明:本站發布的內容(圖片、視頻和文字)以原創、轉載和分享為主,文章觀點不代表本網站立場,如果涉及侵權請聯系站長郵箱:is@yisu.com進行舉報,并提供相關證據,一經查實,將立刻刪除涉嫌侵權內容。