Monday, January 5, 2015

Remove Duplicates from Sorted List II (LeetCode Linked List)

Question: 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.

Idea: First add a dummy node at the front of the input list, since the head node may also be removed.  Then use a pointer "cur" to traverse the list. For each "cur", check whether the next a few elements are duplicates by starting an runner from cur.next.next and compare the value with cur.next. If the runner ran 0 step, means no duplicates, otherwise skip the nodes the runner has passed.

Time: O(n) Space: O(1)

Code:
 public class Solution {  
   public ListNode deleteDuplicates(ListNode head) {  
     if(head==null||head.next==null)  
       return head;  
     ListNode dummy=new ListNode(0);  
     dummy.next=head;  
     ListNode cur=dummy;  
     while(cur.next!=null)  
     {  
       ListNode start=cur.next;  
       ListNode runner=start.next;  
       while(runner!=null&&runner.val==start.val)  
         runner=runner.next;  
       if(start.next=runner)  
         cur=start;  
       else  
         cur=runner;  
     }  
     return dummy.next;  
   }  
 }  

No comments:

Post a Comment