演算法2：鏈表的逆轉
- 首先，我們以單鏈表為例子進行演示。總所周知，單鏈表的每個節點都會持有當前節點的下一個節點的對象引用，即next。現在的題目是：「設計一個演算法，逆轉一個已知的單鏈表」。解題思路是：單鏈表是有序的，即知道一個節點，那麼我們就可以確認當前節點（node）的下一個節點(next)，即node持有next對象引用。如果反過來，next持有node，那不就是逆轉嗎？
package code.code_02; /** * 題目：設計一種演算法，可以逆轉單鏈表 */ public class SingleNodeList { //單鏈表 private static class Node { public int data; public Node next; Node (int _data){ this.data = _data; } public int getData() { return data; } } //循環的方式逆轉 public static Node reverseNode (Node node) { if (node == null) { System.out.println("鏈表不存在"); } //標記前一個已經完成逆轉的節點 Node prev = null; //標記下一個待逆轉的節點 Node next = null; do { //步驟一 //記錄當前節點的下一個節點，因為它是下一個待逆轉的節點。 //如果不標記，執行步驟二會導致可達性分析無法完成，導致第一個節點完成逆轉後剩餘節點被記憶體回收 next = node.next; //步驟二 // 進行節點逆轉操作 //第一次進入，當前節點將會變成逆轉後的最後一個節點。而最後一個節點的next將會指向null //再次進入的時候，因為第一次執行了步驟三，prev將會變成上一個已經完成逆轉的節點，那麼它自然變成當前節點逆轉後的下一個節點 node.next = prev; //步驟三 //因為當前node已經逆轉完成，把它標記並為下一個節點的後繼節點做準備。 //第二次進入的時候在步驟二中調用 prev = node; //步驟四 //此時的node引用移動到逆轉前當前節點的下一個節點，next已經在步驟一中記錄 node = next; } while(node != null); //此處為什麼要返回prev，而不是返回當前節點node呢？ //因為最後一個節有值點為4, 而他的下一個節點為null. 我們需要的是鏈表中實際存在的節點 return prev; } //遞歸的方式逆轉鏈表 public static Node reverseNode2 (Node curNode, Node preReverseNode, Node next) { if (curNode == null) { return curNode; } curNode.next = preReverseNode; preReverseNode = curNode; curNode = next; //逆轉後需要再次確認當前待逆轉的節點是不是null,如果是null說明已經是逆轉前的最後一個油值節點4的下一個節點了。 // 那麼我們只要返回最後一個有值節點即可，因為我們需要的是鏈表中實際存在的節點 return curNode != null ? reverseNode2(curNode, preReverseNode, curNode.next) : preReverseNode; } public static void printNode (Node node) { if (node == null) { System.out.println("鏈表不存在"); } System.out.println("當前鏈表的值為： " + node.getData()); //遞歸的方式逐層列印Node的子節點 if(node.next != null) { printNode(node.next); } } public static void main(String[] args) { //生成單鏈表 Node n = new Node(1); n.next = new Node(2); n.next.next = new Node(3); n.next.next.next = new Node(4); System.out.println("列印循環逆轉前的鏈表: ================================"); printNode(n); n = reverseNode(n); System.out.println("列印循環逆轉後的鏈表: ================================"); printNode(n); Node n1 = new Node(1); n1.next = new Node(2); n1.next.next = new Node(3); n1.next.next.next = new Node(4); System.out.println("列印遞歸逆轉前的鏈表: ================================"); printNode(n1); n1 = reverseNode2(n1, null, n1.next); System.out.println("列印遞歸逆轉後的鏈表: ================================"); printNode(n1); } }
列印結果為：
-
列印循環逆轉前的鏈表: ================================ 當前鏈表的值為： 1 當前鏈表的值為： 2 當前鏈表的值為： 3 當前鏈表的值為： 4 列印循環逆轉後的鏈表: ================================ 當前鏈表的值為： 4 當前鏈表的值為： 3 當前鏈表的值為： 2 當前鏈表的值為： 1 列印遞歸逆轉前的鏈表: ================================ 當前鏈表的值為： 1 當前鏈表的值為： 2 當前鏈表的值為： 3 當前鏈表的值為： 4 列印遞歸逆轉後的鏈表: ================================ 當前鏈表的值為： 4 當前鏈表的值為： 3 當前鏈表的值為： 2 當前鏈表的值為： 1 Process finished with exit code 0
- 既然是設計鏈表的逆轉，當然是要區分單鏈表和雙鏈表的。那麼雙鏈表又改如何設計呢？其實，原理一致，只不過雙鏈表的每個節點會有一個last和next節點對象的引用而已。理解了單鏈表，那麼改成雙鏈表也就非常簡單了
package code.code_02; public class DoubleNodeList { //雙鏈表 private static class Node { public int data; public Node last; public Node next; Node (int _data){ this.data = _data; } public int getData() { return data; } } public static Node reverseDoubleNodeList (Node node, Node prev) { if (node == null) { System.out.println("當前node節點為null"); return node; } //記錄當前節點的上一個節點，下一個節點，為逆轉當前節點做準備 //如果不記錄,當前節點逆轉後會導致數據丟失 Node last = node.last; Node next = node.next; //逆轉當前節點 node.next = last; node.last = next; //prev記錄當前已經完成逆轉的節點，為下一次遞歸做準備 //因為下一次遞歸的時候，我們需要記錄最新的完成逆轉的節點，而prev是為了記錄已經完成逆轉的節點 prev = node; //完成逆轉後, 當前節點node會移動到下一個節點 node = next; //如果逆轉前進入的節點是最後一個有值節點，那麼你轉完以後node會來到null的位置 //此時,我們不需要對node==null的節點進行逆轉，因此只需要返回最後一次完成逆轉的節點即可 //也許，prev會有歧義，我們可以換個合適的名稱來代替prev, 比如preReversedNode return node != null ? reverseDoubleNodeList(node, prev):prev; } public static void printNode (Node node) { if (node == null) { System.out.println("鏈表不存在"); } Node last = node.last; Node next = node.next; System.out.println("當前節點的值為： " + node.getData() + ", 上一個節點值為：" + (last != null ? last.getData():null) + ", 下一個節點為： " + (next !=null ? next.getData():null)); //遞歸的方式逐層列印Node的子節點 if(next != null) { printNode(next); } } public static void main(String[] args) { //構造出5個雙鏈表節點 Node node = new Node(0); Node node1 = new Node(1); Node node2 = new Node(2); Node node3 = new Node(3); Node node4 = new Node(4); node.next = node1; //node1節點 node1.last = node; node1.next = node2; //node2節點 node2.last = node1; node2.next = node3; //node3節點 node3.last = node2; node3.next = node4; //node4節點 node4.last = node3; System.out.println("逆轉前node的hash值為" + node.hashCode()); System.out.println("========================測試逆轉前的雙鏈表============"); printNode(node); //此處為什麼需要一個node來接受逆轉後的值呢？ //其實說是逆轉，實際上是更新了記憶體中每一個對象的的值,並且更改了每一個node的指向。類似於生成了一個新對象 //我們可以根據逆轉前，逆轉後的node的hash值進行確認 //而實際開發中，如果只是一個object對象，比如set了一些變數值, 那麼無法接受值（此處需要理解） node =reverseDoubleNodeList(node, null); System.out.println("逆轉後node的hash值為" + node.hashCode()); System.out.println("========================測試逆轉後的雙鏈表============"); printNode(node); } }
列印結果如下
逆轉前node的hash值為1163157884 ========================測試逆轉前的雙鏈表============ 當前節點的值為： 0, 上一個節點值為：null, 下一個節點為： 1 當前節點的值為： 1, 上一個節點值為：0, 下一個節點為： 2 當前節點的值為： 2, 上一個節點值為：1, 下一個節點為： 3 當前節點的值為： 3, 上一個節點值為：2, 下一個節點為： 4 當前節點的值為： 4, 上一個節點值為：3, 下一個節點為： null 逆轉後node的hash值為1956725890 ========================測試逆轉後的雙鏈表============ 當前節點的值為： 4, 上一個節點值為：null, 下一個節點為： 3 當前節點的值為： 3, 上一個節點值為：4, 下一個節點為： 2 當前節點的值為： 2, 上一個節點值為：3, 下一個節點為： 1 當前節點的值為： 1, 上一個節點值為：2, 下一個節點為： 0 當前節點的值為： 0, 上一個節點值為：1, 下一個節點為： null Process finished with exit code 0
