[leetcode] 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.

困倦时不要解题,这题做了3遍才AC。

一个bonus,删掉多余的node,以免内存溢出。

我用了superHead的技巧,不用再单独判断链表的起始情况。

查看当前节点和下一个节点,如果相同,将isDuplicated置1.当遇到当前节点和下一节点不同时,看isDuplicated的值,如果是1,则忽略掉它,把isDuplicated置0.如果是0,证明当前节点没有重复,连入结果链表中。

/**
 * 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 NULL;
        ListNode * superHead = new ListNode(0);
        superHead->next = head;
        ListNode * start;
        ListNode * p;
        start = superHead;
        p = head;
        bool isDuplicated = false;
        while(p->next != NULL){
            if(p->next->val != p->val){
                if(isDuplicated == false){
                    if(start->next != p){
                        //we need to del some nodes
                        ListNode * tmp = start->next->next;
                        ListNode * prev = start->next;
                        while(tmp != p){
                            delete prev;
                            prev = tmp;
                            tmp = tmp->next;
                        }    
                        delete prev;
                    }
                    start->next = p;// warning: shall we del the removed notes?
                    start = start->next;
                }
                isDuplicated = false;
            }
            else{
                isDuplicated = true;
            }
            p = p->next;
        }
        //1st bug here: return result is not empty
        if(isDuplicated == false){
            start->next = p;
            start = start->next;
        }
        start->next = NULL;
        p = superHead->next;
        delete superHead;
        return p;
    }
};

FireShot Capture - Remove Duplicates from Sorte_ - https___leetcode.com_submissions_detail_25432139_

Leave a comment

Your email address will not be published.

This site uses Akismet to reduce spam. Learn how your comment data is processed.