链表

难度中等

题目描述

解题思路

几乎所有的链表题目，都具有相似的解题思路。

建一个「虚拟头节点」dummy 以减少边界判断，往后的答案链表会接在 dummy 后面
使用 tail 代表当前有效链表的结尾
通过原输入的 head 指针进行链表扫描

我们会确保「进入外层循环时 head 不会与上一节点相同」，因此插入时机：

1. head 已经没有下一个节点，head 可以被插入
2. head 有一下个节点，但是值与 head 不相同，head 可以被插入

作者：AC_OIer
链接：https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list-ii/solution/tong-yong-shan-chu-zhong-fu-jie-dian-lia-od9g/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

Code

class ListNode {
    int val;
    ListNode next;
    ListNode() {
    }
    ListNode(int val) {
        this.val = val;
    }
    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}
public ListNode deleteDuplicates(ListNode head) {
    ListNode dummy = new ListNode();
    ListNode tail = dummy;
    while (head != null) {
        // 进入循环时，确保了 head 不会与上一节点相同
        if (head.next == null || head.val != head.next.val) {
            tail.next = head;
            tail = head;
        }
        // 如果 head 与下一节点相同，跳过相同节点
        while (head.next != null && head.val == head.next.val) head = head.next;
        head = head.next;
    }
    tail.next = null;
    return dummy.next;
}