【力扣82】删除排序链表中的重复元素II

题目

给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。

示例 1：

1 2	输入：head = [1,2,3,3,4,4,5] 输出：[1,2,5]

示例 2：

1 2	输入：head = [1,1,1,2,3] 输出：[2,3]

提示：

链表中节点数目在范围 [0, 300] 内
-100 <= Node.val <= 100
题目数据保证链表已经按升序排列

实现代码

方式一：链表分解

通过将链表分解为重复元素链表和不重复元素链表，最终返回不重复链表即可

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode deleteDuplicates(ListNode head) {

        // 定义两个虚拟链表，p1存放重复节点，p2存放不重复节点
        // 虚拟节点初始val设置为101是因为题目设定的val范围是[-100,100]，所以只要val设定不在这个范围内就不会影响相等元素的判断
        ListNode p1 = new ListNode(101), pp1 = p1, p2 = new ListNode(101), pp2 = p2, p = head;
        while(p != null){
            // 是否元素校验
            // p.val == pp1.val 这个条件很关键，元素存在重复链表中，说明当前元素也是重复元素
            if(p.next != null && p.val == p.next.val || p.val == pp1.val){
                // 重复
                pp1.next = p;
                pp1 = pp1.next;
            }else{
                // 不重复
                pp2.next = p;
                pp2 = pp2.next;
            }
            p = p.next;
        }
        // 与p链表进行断开（分解链表一定要断开）
        pp1.next = null;
        pp2.next = null;
        return p2.next;
    }
}

核心点

ListNode p1 = new ListNode(101), p2 = new ListNode(101)：存放重复元素与不重复元素，val = 101是为了不影响重复元素判断；
p.val == pp1.val：用于过滤掉重复元素；
pp1.next = null; pp2.next = null;：用于断开原链表，分解链表一定要与旧链表断开；

时间复杂度

O(n)

空间复杂度

O(1)

方式二：双指针

使用双指针方式，定义虚拟节点q和索引指针p、p1，p1向前移的同时始终校验前面节点是否相同，相同则一直往前移动直到遇到不同节点，否则将当前节点链虚拟节点上；

难点：如何断定两个节点不相等并且不是重复节点？

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode deleteDuplicates(ListNode head) {

        ListNode q = new ListNode(-1), p = q;
        ListNode p1 = head;
        while (p1 != null) {
            if (p1.next != null && p1.val == p1.next.val) {
                // 检查到重复元素，一直往前走，直到遇到不同元素
                // 单独起一个循环用于解决上面说的难点问题
                while (p1.next != null && p1.val == p1.next.val) {
                    p1 = p1.next;
                }
                // 遇到不同元素，先待到那个位置，是否把当前节点链到新链表还需要判断前面节点是否相同
                // 不是重复节点就先移到那个不同节点上，避免再次循环判定为不同节点
                p1 = p1.next;
                continue;
            }
            // 将节点链到新链表上
            p.next = p1;
            p1 = p1.next;
            p = p.next;
        }
        // 链过来的节点与旧链表进行断开
        p.next = null;
        return q.next;
    }
}