Wednesday, March 11, 2015

83. Remove Duplicates from Sorted List Leetcode Java

83. Remove Duplicates from Sorted List Leetcode

Given a sorted linked list, delete all duplicates such that each element appear only once.
For example,
Given 1->1->2, return 1->2.
Given 1->1->2->3->3, return 1->2->3.
Solution:
Two pointers:
Check if the current.value==pre.value, if yes, skip the current node, and set current.next as the current. if no, link it to the pre.next which will delete all the duplicates between these two nodes and proceed the current. 
Tips: don't forget to set pre.next=null, when the loop finished. Eg. 1->1->1; if we don't set the pre.next=null, it won't delete the last duplicate nodes.  
Time complexity: O(n)
 public ListNode deleteDuplicates(ListNode head) {  
     if(head==null || head.next==null) return head;  
     ListNode cur=head.next;  
     ListNode pre=head;  
     while(cur!=null){  
       if(cur.val!=pre.val){  
         pre.next=cur;  
         pre=cur;  
       }  
       cur=cur.next;  
     }  
     pre.next=null;  
     return head;  
   }  

No comments:

Post a Comment