82. Remove Duplicates from Sorted List II Leetcode Java

82. 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.

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

Solution:

Follow up 83. Remove Duplicates from Sorted List Leetcode

Now,we need to delete all nodes that have duplicates rather than leaving one there.

A preDummy node is needed to avoid processing the special head node. An easy way to check if it is distinct node is that check if the current.val==current.next.val, if yes, loop the current node till next node with different value, and then check if it is equal to its next.val.  eg 1->2->3->3->4->4->5, current:1, current.next: 2, so current is a distinct number, so do 2, when current: 3, current.next: 3 so current is not a distinct value, loop current till new value occurs, which is 4, so current: 4, current.next: 4, so 4 is not a distinct node, then current is 5. After the outer while loop finished, we need to attach the current node to pre node, because the current node will be either the tail node(distinct) or null(tail is not distinct).

Time complexity: O(n)

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