首页 > 代码库 > Remove Duplicates from Sorted List II
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++代码实现：
#include<iostream>#include<new>using namespace std;//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||head->next==NULL) return head; ListNode *p=head->next; ListNode *pre=head; ListNode *ppre=head; ListNode *q=NULL; while(p) { if(p->val!=pre->val) { //要删除头结点的情况，如果pre与ppre都指向头结点，则不需要删除，否则将删除头结点到p之间的所有结点，包括头结点 if(ppre==head&&ppre->val==pre->val&&pre!=ppre) { while(ppre!=p) { q=ppre; ppre=ppre->next; q->next=NULL; delete q; } head=p; ppre=p; pre=p; p=p->next; continue; } else if(ppre->next!=pre) { pre->next=NULL; pre=ppre->next; ppre->next=p; while(pre) { q=pre; pre=pre->next; q->next=NULL; delete q; } pre=p; p=p->next; continue; } ppre=pre; pre=p; p=p->next; } else { pre=p; p=p->next; } } cout<<ppre->val<<endl; cout<<pre->val<<endl; //如果ppre需要删除，肯定是因为指向头结点，否则ppre指向的结点不会与pre相等 if(ppre==head&&ppre->val==pre->val&&ppre!=pre) { while(ppre!=p) { q=ppre; ppre=ppre->next; q->next=NULL; delete q; } return NULL; } else if(ppre->next!=pre) { pre->next=NULL; pre=ppre->next; ppre->next=p; while(pre) { q=pre; pre=pre->next; q->next=NULL; delete q; } } return head; } void createList(ListNode *&head) { ListNode *p=NULL; int i=0; int arr[10]= {6,5,5,4,4,3,3,3,2,2}; for(i=0; i<2; i++) { if(head==NULL) { head=new ListNode(arr[i]); if(head==NULL) return; } else { p=new ListNode(arr[i]); p->next=head; head=p; } } }};int main(){ Solution s; ListNode *L=NULL; s.createList(L); ListNode *head=L; while(head) { cout<<head->val<<" "; head=head->next; } cout<<endl; L=s.deleteDuplicates(L); while(L) { cout<<L->val<<" "; L=L->next; }}
Remove Duplicates from Sorted List II
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。