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.
思路
定义一个前结点p=&dummy,然后分情况讨论cur和cur->next。
1)若cur->next=NULL,则p->next=cur;p=p->next;cur=cur->next
2)cur->next!=NULL,cur->next->val==cur->val,cur移动到不相等的位置。
3)cur->next!=NULL,cur->next->val!=cur->val,操作如1)。
解题
c++版
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42
| * 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 || !head->next) return head; ListNode dummy(-1); ListNode *p=&dummy; ListNode *cur=head,*q; while(cur){ if(!cur->next){ p->next=cur; p=p->next; cur=cur->next; } else{ if(cur->next->val==cur->val){ q=cur->next; while(q and q->val==cur->val){ q=q->next; } cur=q; } else{ p->next=cur; p=p->next; cur=cur->next; } } } p->next=NULL; return dummy.next; } };
|
Python版
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
|
class Solution: def deleteDuplicates(self, head): dummy=ListNode(-1) if not head or not head.next: return head p=dummy cur=head while cur: if not cur.next: p.next=cur p=p.next cur=cur.next else: if cur.val!=cur.next.val: p.next=cur p=p.next cur=cur.next else: q=cur.next while q and q.val==cur.val: q=q.next cur=q p.next=None return dummy.next
|