Description
Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.
给定一个排序链表，删除所有重复的元素只留下原链表中没有重复的元素。
Examples
Input: 1->2->3->3->4->4->5
Output: 1->2->5
Input: 1->1->1->2->3
Output: 2->3
Answer
Use another pointer to traverse the list started from the beginning node head. If detect the duplicate value, then skip the next node and continue comparing with the following node of the next node. After find all the nodes with duplicate values, move the current node to the next node with the new value to delete all the nodes which have the duplicates.
Time Complexity
O(n) since the algorithm is one pass.
Code
C++
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
if(!head || !head->next) return head;
ListNode *dummy = new ListNode(0), *cur;
dummy->next = head;
cur = dummy;
while(cur->next && cur->next->next)
{
if(cur->next->val != cur->next->next->val)
{
cur = cur->next;
continue;
}
while(cur->next && cur->next->next && cur->next->val == cur->next->next->val)
cur->next = cur->next->next;
cur->next = cur->next->next; // Delete this column then it becomes the solution of Remove Duplicates from Sorted List I
}
return dummy->next;
}
};
