Leetcode and Lintcode

Remove Duplicates from Sorted List II

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

Have you met this question in a real interview? Yes
Example
Given 1->2->3->3->4->4->5, return 1->2->5.
Given 1->1->1->2->3, return 2->3.

Leetcode link
Lintcode link

Solution:

Go through the list, use a variable ‘prevPre’ as a ponter to point to the node before previous node.
If the middle two nodes have the same value, delete the two nodes and record the value. Continue on the list, if the following nodes have the same value as this value, delete the following nodes.
Iterate the previous steps untils there are no node behind.

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
28
29
30
31
32
33
/*************************************************************************
	> File Name: RemoveDuplicatesfromSortedListII.java
	> Author: Yao Zhang 
	> Mail: psyyz10@163.com 
	> Created Time: Wed 18 Nov 15:27:20 2015
 ************************************************************************/

public class RemoveDuplicatesfromSortedListII{
	public ListNode deleteDuplicates(ListNode head) {
        if (head == null || head.next == null)
            return head;
        
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode prevPre = dummy;
        
        while (prevPre.next != null && prevPre.next.next != null){
            if (prevPre.next.val == prevPre.next.next.val){
                int value = prevPre.next.val;
                prevPre.next = prevPre.next.next.next; 
                
                while (prevPre.next != null && prevPre.next.val == value){
                    prevPre.next = prevPre.next.next;
                }
            }
            else{
                prevPre = prevPre.next;
            }
        }
        
        return dummy.next;
    }
}