[LeetCode] 82. Remove Duplicates from Sorted List II

Posted on | In

Problem

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

Example 1:

1
2
Input: 1->2->3->3->4->4->5
Output: 1->2->5

Example 2:

1
2
Input: 1->1->1->2->3
Output: 2->3

Explanation

  1. We need to check if the current element is same as its previous element and its next element, so we need to create a dummy node, and a pre pointer initially points at the dummy node, a current pointer initially points at the first element, and we compare current pointer element with pre pointer element and current.next element.

  2. If the current element is not the same as its previous and next element, then we need to store it into a linkedlist, so we can store the first distinct element into dummy.next, at the end we can return dummy.next.

  3. After we store the matching current element, we need to move pre and cur pointers to point at the next element. Because now cur points at the correct next element and we want to cut off the result list and input list, we can set pre.next to null, one example is input list is [1, 2, 2], we want the result list to be [1]. Also, initially, the dummy.next is null and it’s not pointing to the head of the input linkedlist.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode dummy = new ListNode(-1);
        ListNode pre = dummy;
        ListNode res = dummy;
        ListNode cur = head;
        while (cur != null) {
            if ((pre == dummy || cur.val != pre.val) && (cur.next == null || cur.val != cur.next.val)) {
                res.next = cur;
                res = res.next;
            }
            pre = cur;
            cur = cur.next;
            pre.next = null;
        }
        
        return dummy.next;
    }
}