Question

link

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

For example,
Given 1->2->3->3->4->4->5, return 1->2->5.
Given 1->1->1->2->3, return 2->3.

Stats

Frequency 3
Difficulty 3
Adjusted Difficulty 2
Time to use ----------

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Analysis

This is a very important question. Solution is a little tricky with boundary cases that need consider.

My code works, but there is an extremely good solution posted below.

Code

First, my code

public ListNode deleteDuplicates(ListNode head) {
    ListNode preHead = new ListNode(0);
    preHead.next = head;
    ListNode left = preHead, right = head;
    while (right != null) {
        if (right.next == null || right.val != right.next.val) {
            // next is differnet from previous
            left = right;
            right = right.next;
        }
        else {
            // next is same as previous
            while (right.next != null && right.val == right.next.val)
                right = right.next;
            left.next = right.next;
            right = right.next;
        }
    }
    return preHead.next;
}

Second, a great solution from this blog.

public ListNode deleteDuplicates(ListNode head) {
    if(head == null) return head;
    ListNode helper = new ListNode(0);
    helper.next = head;
    ListNode pre = helper, cur = head;
    while(cur!=null)
    {
        while(cur.next!=null && pre.next.val==cur.next.val)
            cur = cur.next;
        if (pre.next == cur)
            pre = pre.next;
        else
            pre.next = cur.next;
        cur = cur.next;
    }
    return helper.next;
}