用虚拟头结点，为什么要删除元素是头结点head 和 dummyHead 的值不一样
来源：5-1 Leetcode中和链表相关的问题
夏落若
2019-05-30
LeetCode203删除节点
// 方法2：虚拟头结点
public ListNode removeElements_2(ListNode head, int val) {
ListNode dummyHead = new ListNode(-1);
dummyHead.next = head;
ListNode prev = dummyHead;
while (prev.next != null) {
if (prev.next.val == val) {
prev.next = prev.next.next;
System.out.println();
System.out.println("== val head ; " + head);
System.out.println("== val dummHead.next : " + dummyHead.next);
} else {
prev = prev.next;
System.out.println();
System.out.println("head : " + head);
System.out.println("dummHead.next : " + dummyHead.next);
}
}
return dummyHead.next;
}
测试代码：
public static void main(String[] args) {
int[] arr = {6, 1, 2};
ListNode head = new ListNode(arr);
Solution_203 solution = new Solution_203();
ListNode ret = solution.removeElements_2(head, 6);
System.out.println(ret);
测试数组是{6, 1, 2}打印：
== val head ; 链表：6->1->2->null
== val dummHead.next : 链表：1->2->null
head : 链表：6->1->2->null
dummHead.next : 链表：1->2->null
head : 链表：6->1->2->null
dummHead.next : 链表：1->2->null
链表：1->2->null
测试数组是{1, 6, 2}打印：
head : 链表：1->6->2->null
dummHead.next : 链表：1->6->2->null
== val head ; 链表：1->2->null
== val dummHead.next : 链表：1->2->null
head : 链表：1->2->null
dummHead.next : 链表：1->2->null
链表：1->2->null
不理解为什么要删除元素在头结点head和dummHead.next不同，要删除元素不在头结点二者相同？
1回答
-
以链表1->2->3->4->5为例。
加上虚拟头结点，是 dummy->1->2->3->4->5。注意，head是指向1的，所以是这样的：
dummy->1->2->3->4->5 ^ | head
==========
如果删除1（头结点），这个链表变成这个样子：
dummy->2->3->4->5 ^ | head->1
仔细思考一下，为什么是这个结果？因为我们把待删除节点的前一个节点，直接和待删除节点的后一个节点连起来，达到了删除节点的目的。
或者跟一遍程序，再仔细理解一下？
此时，顺着dummyHead走，链表是2->3->4->5
顺着head走，链表是1->2->3->4->5
==========
如果删除3（非头结点），这个链表变成这个样子：
dummy->1->2->4->5 ^ ^ | | head 3
仔细思考一下，为什么是这个结果？因为我们把待删除节点的前一个节点，直接和待删除节点的后一个节点连起来，达到了删除节点的目的。
或者跟一遍程序，再仔细理解一下？
此时，顺着dummyHead走，链表是1->2->4->5
顺着head走，链表还是1->2->4->5
==========
但是，你可以看到，我们删除的节点还连接着原来的链表。
所以：
这就是我在课程中实现代码，删除的节点手动为其next赋空的原因。手动让他和原来的链表断开，这样，大家可以很清晰的理解，这个节点被删除了。再仔细看一下，理解一下，课程中的节点删除的方法？
但是，如果不手动置空，程序是没有错误的。首先逻辑上，这个节点确实删除了。其次，内存上，被删除的节点是引用不可达的，所以会慢慢被GC垃圾回收。不过这属于Java内存管理相关的内容了，不再这个课程的范围里：）
加油！：）
222019-06-01
相似问题