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.

C++:
01 void Enlist(ListNode** head, ListNode** tail, ListNode* tmp)
02 {
03     if(tmp==NULL)
04         return;
05     if((*head)==NULL){
06         (*head)=(*tail)=tmp;
07     }else{
08         (*tail)->next=tmp;
09         *tail=tmp;
10     }
11 }
12 
13  ListNode *deleteDuplicates(ListNode *head)
14  {
15      if(head==NULL)
16          return NULL;
17      ListNode* hd=NULL;
18      ListNode* tl=NULL;
19      ListNode* tmp=head;
20      int data=0;
21      while(tmp!=NULL){
22          if((tmp==head)||(tmp->val!=data)){
23             if((tmp->next==NULL)||
24                (tmp->val!=tmp->next->val)){
25                 Enlist(&hd,&tl,tmp);
26             }
27          }
28          data=tmp->val;
29          tmp=tmp->next;
30     }
31     if(hd==NULL)
32         return NULL;
33     tl->next=NULL;
34     return hd;
35 }
Advertisements
This entry was posted in Array and linked list. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s