4/15/2014

Leetcode -- Remove Duplicates from Sorted List II

Ideally, we should delete those removed nodes
 /**  
  * Definition for singly-linked list.  
  * struct ListNode {  
  *   int val;  
  *   ListNode *next;  
  *   ListNode(int x) : val(x), next(NULL) {}  
  * };  
  */  
 class Solution {  
 public:  
   ListNode *deleteDuplicates(ListNode *head) {  
     if(head == NULL) {  
       return NULL;  
     }  
     ListNode * dummy = new ListNode(0);  
     dummy->next = head;  
     ListNode * slow = dummy;  
     ListNode * moving = head->next;  
     bool isDuplicate = false;  
     while(moving != NULL ) {  
       if(slow->next->val == moving->val) {  
         isDuplicate = true;  
         moving = moving->next;  
       } else {  
         if(isDuplicate) {  
           slow->next = moving;  
           isDuplicate = false;  
           moving = moving->next;  
         } else {  
           moving = moving->next;  
           slow = slow->next;  
         }  
       }  
     }  
     if(isDuplicate) {  
       slow->next = moving;  
     }  
     return dummy->next;  
   }  
 };  

No comments: