首页 > 代码库 > Remove Duplicates from Sorted List II

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.

/** * 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* newHead = new ListNode(-1);        newHead->next = head;        ListNode* pre = newHead;        ListNode* cur = head;        bool duplicated = false;// if has duplicates        while(cur->next){            if(cur->val == cur->next->val){                cur = cur->next;                duplicated = true;            }else{                if(duplicated){                    while(pre->next != cur->next){                        ListNode* tmp = pre->next;                        pre->next = pre->next->next;                        delete tmp;                    }                //     pre->next = cur->next;                    duplicated = false;                }else{                    pre->next = cur;                    pre = cur;                }                cur = cur->next;            }        }        if(duplicated){            pre->next = nullptr;        }        return newHead->next;    }};

 

Remove Duplicates from Sorted List II