Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.
For example,
Given
Given
Given
1->2->3->3->4->4->5
, return 1->2->5
.Given
1->1->1->2->3
, return 2->3
.
Analysis:
class Solution {
public:
ListNode *deleteDuplicates(ListNode *head) {
ListNode* dummyHead = new ListNode(0);
dummyHead->next = head;
//use dummy head to make it easy to handle head node which is duplicate
ListNode* prev = dummyHead;
ListNode* curr = head;
while(curr != NULL)
{
//When find a node whose value is equal to its next node
if (curr->next != NULL && curr->val == curr->next->val)
{
//remove all its next nodes
while(curr != NULL && curr->next != NULL && curr->val == curr->next->val)
{
ListNode* next = curr->next;
curr->next = curr->next->next;
delete next;
}
//then remove itself.
ListNode* tmp = curr;
prev->next = curr->next;
curr = curr->next;
delete tmp;
}
else
{
//otherwise, move to next node
prev = curr;
curr = curr->next;
}
}
return dummyHead->next;
}
};
No comments:
Post a Comment