关于单链表反转的一点整理
- 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; 这种写法也是一个一样的效果，但是行为是不一样的行为。 }
如果还有不对，欢迎指正。
