關於單鏈表反轉的一點整理
- 2019 年 10 月 3 日
- 筆記
單鏈表的反轉困擾了我好幾天了。今天終於一通百通了，特地記錄一下，免得以後又忘記了。腦子笨，只能靠這種辦法了。
之前網上的一種做法是這樣的：
1 public void reversList(){ 2 Node pre = null; 3 Node next = null; 4 while (head != null) { 5 next = head.next; 6 head.next = pre; 7 pre = head; 8 head = next; 9 } 10 head = pre; 11 }
核心的程式碼就是這一段：
但實際上做種做法是錯誤的。我們先看看反轉之後的情況。
一遍一遍遍歷的過程是這樣的。每一行就是一次遍歷。
1 Node [data=4, next=Node [data=3, next=Node [data=2, next=Node [data=1, next=Node [data=null, next=null]]]]] 2 Node [data=3, next=Node [data=2, next=Node [data=1, next=Node [data=null, next=null]]]] 3 Node [data=2, next=Node [data=1, next=Node [data=null, next=null]]] 4 Node [data=1, next=Node [data=null, next=null]] 5 Node [data=null, next=null]
這個實際上我沒辦法遍歷，我是用最笨的辦法一點一點還原出來的，如下：
1 System.out.println(list.getHead()); 2 System.out.println(list.getHead().next); 3 System.out.println(list.getHead().next.next); 4 System.out.println(list.getHead().next.next.next); 5 System.out.println(list.getHead().next.next.next.next);
我們再看看鏈表在反轉之前是什麼樣子的，同樣適用一樣的笨辦法：
1 Node [data=null, next=Node [data=1, next=Node [data=2, next=Node [data=3, next=Node [data=4, next=null]]]]] 2 Node [data=1, next=Node [data=2, next=Node [data=3, next=Node [data=4, next=null]]]] 3 Node [data=2, next=Node [data=3, next=Node [data=4, next=null]]] 4 Node [data=3, next=Node [data=4, next=null]] 5 Node [data=4, next=null]
現在看來，反轉前後，鏈表中有效的值只是大概相等而已，實際上並不一致。其在首尾節點上也是不一樣的。
這種思路一開始是從head開始遍歷開始反轉的，但是其實head是一個指針節點，真正有效的節點是head.next，應該從這個開始遍歷替換，所以真正應該遍歷的當前節點其實是 head.next。而應該先保存的當前節點的下一個節點其實是 head.next.next。這是第一個錯誤。
第二個錯誤是：用來保存前一個節點的變數，不應該是Node pre = null;而應該是Node pre = new Node(null)。這兩種寫法，完全是兩個不同的東西。Node pre = null 完全就是只有一個棧空間里的引用而已，根本沒有指向堆里的空間，事實上這就不是一個對象。而Node pre = new Node(null)這種寫法，是一種實打實的對象，是真正的引用指向了堆裡面的空間了。所以當第二步 head.next = pre;（正確的是：head.next.next = pre.next）的時候，得到的結果就完全不一樣了。如果pre=null；那就是把前一個有效節點都置為null了，這個對象就死了，真正要做的是斷開前一個節點與後一個節點之間的指針連接，所以要置為null的是 pre.next，pre的指針域是null，而不是pre本身是null。這是兩碼事。這裡我第一次看到網上的答案時，還不明白，為什麼不可以直接直接Node pre = null，這下才算是明白。
第一步第二步都錯了之後，後面的步驟肯定也是錯的了。
那為什麼最後還可以得出一個對的假象呢？即：
Node [data=4, next=Node [data=3, next=Node [data=2, next=Node [data=1, next=Node [data=null, next=null]]]]]
最後得到的鏈表是這個，
這就是因為第二次循環之後，pre的next域，被恰好填充了對象，但是這個對象卻是一個錯誤的對象如：
Node [data=1, next=Node [data=null, next=null]] 具體怎麼錯，以後慢慢研究吧。
正確的思路應該是，從head的next域指向的第一個有效節點開始遍歷。可以直接在原來的鏈表上進行遍歷替換。最後用反轉之後的鏈表的第一個有效節點再接上head.next，這樣head的指針域就指向了反轉之後的鏈表。如下：
1 public void reversList(){ 2 Node pre = new Node(null); 3 //Node pre = null;錯誤寫法 4 Node next = null; 5 6 while (head.next != null) {//從第一個有效節點開始遍歷 7 next = head.next.next;//先記錄當前節點的下一個節點 8 head.next.next = pre.next;//將當前節點的指針域置空 9 pre.next = head.next;//將下一節點的指針域，指向當前節點，完成節點交換 10 head.next = next;//往後移動 11 } 12 13 head.next = pre.next;//最後把反轉後的節點與頭結點聯繫上。最終得到完整的反轉之後的鏈表。 14 }
或者也。可以新創建一個新的鏈表，然後遍歷老鏈表後，把節點添加到新鏈表的第一個有效節點位置。最後返回新的鏈表，或者用新的鏈表覆蓋head。也許這樣比較容易理解：
public void reversList(){ Node temp = head.next;//設置一個臨時變數保存第一個有效節點 Node newHead = new Node(null);//設置一個新的頭結點 Node next = null;//用於保存下一個節點 while(temp != null){ next = temp.next;//保存當前節點的下一個節點 temp.next = newHead.next;//將當前節點的指針域置空 newHead.next = temp;//始終把當前節點插入到新鏈表的第一個有效節點的位置 temp = next;//向後移動一個節點 } head = newHead;//最後把新的鏈表的頭節點賦值給原節點的頭結點，完成兩個鏈表的合併 // head.next = newHead.next; 這種寫法也是一個一樣的效果，但是行為是不一樣的行為。 }
如果還有不對，歡迎指正。