82 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.
Solution
/**
* 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 head;
ListNode *dummy = new ListNode(0);
dummy->next = head;
ListNode *ptail = dummy, *p = head;
int val;
while (true) {
if ( p->next == NULL ) { ptail->next = p; break; }
// note the difference between the following two situations:
// duplicate
if ( p->val == p->next->val ) {
val = p->val;
while ( p->val == val ) {
p = p->next;
if ( p == NULL ) break;
}
if ( p == NULL ) { ptail->next = p; break; }
}
// vs. non-duplicate
else {
ptail->next = p;
if ( p == NULL ) break;
ptail = p;
p = p->next;
}
}
return dummy->next;
}
};
Notes
Pay attention to a lot of DETAILS!
ptail->next is different for "duplicate" case and "non-duplicate case":
- duplicate case: ptail->next does not necessarily point to the first node after the consecutive duplicate nodes. ptail remains the same, we will examine pointer p in the next loop!
Inappropriate linkage would give the erroneous answer: [1,2,4,4,5].corner case: [1,2,3,3,4,4,5]
- non-duplicate case: ptail->next points to the next "unique nodes";
Another solution
/**
* 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 or head->next == NULL ) return head;
ListNode *dummy = new ListNode(0);
ListNode *tail = dummy;
ListNode *last = head, *p = head->next;
while ( p != NULL ) {
if ( p->val != last->val ) {
tail->next = last;
tail = tail->next;
}
else {
while ( p != NULL and p->val == last->val ) p = p->next;
if ( p == NULL ) { last = NULL; break;}
}
last = p;
p = p->next;
}
tail->next = last;
return dummy->next;
}
};
Notes
这个解法中注意tail->next = last
的处理。