[82] Remove Duplicates from Sorted List II

雖然邊看著世足賽邊寫還可以前前後後把它寫出來

但是真的面試的時候又會腦袋一片空白吧.....(眼神死)

先放個初版

/**

* Definition for singly-linked list.

* struct ListNode {

* int val;

* struct ListNode *next;

* };

*/

struct ListNode* deleteDuplicates(struct ListNode* head){

if (head == NULL || head->next==NULL)

return head;

struct ListNode* p0=head;

struct ListNode *p1,*p2;

while(p0!= NULL && p0->next !=NULL)

{

p1=p0;

p2=p1->next;

if (p1->val != p2->val)

{

if(p2->next !=NULL && p2->next->val != p2->val)

{

p0=p1->next;

continue;

}

else if(p2->next !=NULL && p2->next->val == p2->val)

{

while (p2->next !=NULL && p2->next->val == p2->val)

p2=p2->next;

p1->next = p2->next;

}

else if (p2->next==NULL)

break;

}

else if (p1->val == p2->val) // only happen at head?!

{

while (p2->next !=NULL && p2->next->val == p2->val)

p2=p2->next;

if (p0==head)

{

head=p2->next;

p0=head;

}

else

p0=p2->next;

}

}

return head;

}

修一修可以改短幾行，但是有必要嗎XD

看了別人的submit，看起來好精簡喔QQ 是我想的太難了嗎><

其實不用這麼小心的一直考慮嗎.......

/**

* Definition for singly-linked list.

* struct ListNode {

* int val;

* struct ListNode *next;

* };

*/

struct ListNode* deleteDuplicates(struct ListNode* head){

if (head == NULL || head->next==NULL)

return head;

struct ListNode* p0=head;

struct ListNode *p2;

while(p0!= NULL && p0->next !=NULL)

{

p2=p0->next;

if (p0->val != p2->val)

{

if(p2->next !=NULL && p2->next->val != p2->val)

{

p0=p0->next;

continue;

}

else if (p2->next !=NULL && p2->next->val == p2->val)

{

while (p2->next !=NULL && p2->next->val == p2->val)

p2=p2->next;

p0->next = p2->next;

}

else if (p2->next==NULL)

break;

}

else if (p0->val == p2->val) // only happen at head

{

while (p2->next !=NULL && p2->next->val == p2->val)

p2=p2->next;

head=p2->next;

p0=head;

}

}

return head;

}

看起來是被head (or dummy) 給卡住了嗎QQ

貼一下別人的code ，等頭腦比較清醒再來想一下><

val 不一樣的時候才更新pre，val一樣的時候只更新curr，因為不確定拿掉前一輪duplicates後，後一輪還不知道是不是duplicate，所以pre 只在val 不一樣的時候才更新。

struct ListNode* deleteDuplicates(struct ListNode* head){

    struct ListNode *dummy = malloc(sizeof(struct ListNode));
    
    dummy->next = head;
    
    struct ListNode *prev = dummy;
    struct ListNode *curr = head;
    
    while(curr != NULL && curr->next != NULL){
        if(curr->val == curr->next->val){
            while(curr->next != NULL && curr->val == curr->next->val){
                curr->next = curr->next->next;
            }
            prev->next = curr->next;
        }
        else{
            prev = prev->next;
        }
        curr = curr->next;
    }
    
    return dummy->next;

}