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.
Before I get started, I should write down what I know for now, its a singly-linked-list related problem, and its already been sorted, that mean every duplicate numbers is next to each other. note that it requires to remove all the duplicates, seems like an easy job.
ListNode *deleteDuplicates(ListNode *head) {
ListNode* current, *prev;
ListNode base = ListNode(-10);
base.next = head;
current = &base; prev = NULL;
while (current && current->next){
if (current->val == current->next->val){
while (current->next && current->val == current->next->val){
current = current->next;
}
prev->next = current->next;
current = current->next;
}else {
prev = current;
current = current->next;
}
}
return base.next;
}
By inserting a dummy node with some invalid number(I choose -1 at first, but a test case uses -1 as 1st val as well...wtf) before head is a good trick, it'll allow you to delete head of current list. anyway, operating linked list in c++ is much convenient then c. In c, you can't change list structure by not involving any double pointer.