LeetCode题解-82.删除排序链表中的重复元素II

题目描述

给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中没有重复出现的数字。

示例1:

输入: 1->2->3->3->4->4->5

输出: 1->2->5

示例2:

输入: 1->1->1->2->3

输出: 2->3

解题思路

根据题意可知，如果相连的三个数都不相等，则中间那个数就是我们要的没有重复出现的数字。使用三个指针分别指向相连的三个数，然后遍历链表，把符合条件的数放到新链表里即可。

代码

public static ListNode deleteDuplicates(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode prev = null;
        ListNode current = head;
        ListNode next = current.next;
        ListNode pointer = new ListNode(-1);
        ListNode newHead = pointer;
        while (next != null) {
            // 第一个节点特殊处理，如果第一个节点和他的下一个节点不相等，则第一个节点也是满足条件的
            if (prev == null && current.val != next.val || prev != null && prev.val != current.val && current.val != next.val) {
                pointer.next = new ListNode(current.val);
                pointer = pointer.next;
            }
            prev = current;
            current = next;
            next = current.next;
        }
        if (prev.val != current.val) {
            pointer.next = new ListNode(current.val);
        }
        return newHead.next;
    }