leetcode链表总结之虚拟(哑)节点_链表哑节点

虚拟(哑)节点(dummy node)

在链表的操作中，添加一个哑节点(dummy),让它的指针指向链表的头节点。

ListNode dummy = new ListNode(val, head);
return dummy.next;
1
2

好处：

1. 省略头节点为空时的情况的判断；
2. 头节点和其他节点进行同样的操作时，由于头节点没有前一个节点，需要对这种情况进行单独判断，但加入虚拟节点以后，头节点就可以当作普通节点看待。

eg1：leetcode–203.移除链表的元素
203.移除链表的元素

示例2属于头节点为空的情况；示例3属于要删除头节点的情况。如果不加入虚拟节点，这两种情况都需要单独考虑，加入虚拟节点就不一样了。

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        ListNode dummy = new ListNode(1, head); //在头节点前加入虚拟节点
        ListNode temp = dummy;
        while (temp.next != null) {
            if (temp.next.val == val) 
                temp.next = temp.next.next;
            else 
                temp = temp.next;
        }
        return dummy.next;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

说明：

1. 给虚拟节点赋值1是因为没有单独给下一个节点赋值的构造方法，当然也可以这样写

ListNode dummy = new ListNode(); //虚拟节点的值默认为0
dummy.next = head;
1
2

2. 由于虚拟节点不作为最终结果返回，所以返回值一般是dummy.next。
3. 当 head == null时，即temp.next =null，不进入循环，直接返回dummy.next，dummy.next = head = null。符合题意。
4. 当情况为示例3所示时，首先头节点不为空，进入循环

• 头节点的值等于val，删除头节点，让temp指向第2个节点;
• 第2个节点的值等于val,删除第2个节点，让temp指向第3个节点;
• …
• 第4个节点删除后，temp.next = null，不符合while循环条件，直接退出；
• 由于temp节点始终未移动，所以dummy.next = temp.next = null，返回null，结束。

eg2：leetcode–82. 删除排序链表中的重复元素 II
82. 删除排序链表中的重复元素 II

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode dummy = new ListNode(-101,head);
        ListNode cur = dummy;
        while (cur.next != null && cur.next.next != null) {
            if (cur.next.val != cur.next.next.val) {
                cur = cur.next;
            } else {
                int number = cur.next.val;
                cur.next = cur.next.next.next;
                while (cur.next != null && (cur.next.val == number)) {  
                    cur.next = cur.next.next;
                }
            } 
        }
        return dummy.next; 
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

说明：

1. 加入虚拟节点的作用是可以保证如果链表前面(包括头节点)的大部分节点都是同样的值时，可以让遍历的节点cur固定在哑节点不动，只改变其指向。
2. 此题的关键在于有多个节点都是同一个数怎么办？因为我们删除其中一个节点，就无法判断下一个节点的数是否重复，所以技巧是当出现重复的值时，将这个值保存下来，遍历链表直到节点的值不等于这个重复值为止。