【leetcode】Remove Duplicates from Sorted List II (middle)

4290 단어 LeetCode
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 .
 
아이디어:
일반적인 사고방식, 관건: 가짜 머리로 새 체인 머리의 번거로움을 피한다.
ListNode *deleteDuplicates2(ListNode *head) {

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

        ListNode fakehead(0); //                 

        ListNode * newtail = &fakehead;

        ListNode * p = head;

        int preval = head->val + 1; //                        



        while(p != NULL)

        {

            if(p->val == preval) //     

            {

                p = p->next;

            }

            else //   

            {

                preval = p->val;

                if(p->next != NULL && p->next->val == preval) //                 

                 {

                    p = p->next->next;

                }

                else  //            

                {

                        newtail->next = p;

                        p = p->next;

                        newtail = newtail->next;

                        newtail->next = NULL;

                }

            }

        }

        return fakehead.next;

    }

 
대신은 위두부의 방법을 필요로 하지 않고 지침의 주소를 이용했다.주소에 놓인 바늘을 직접 변경합니다.
 class Solution {

public:

    ListNode *deleteDuplicates(ListNode *head) {

        ListNode** p = &head;

        while(*p && (*p)->next) {

            ListNode* p1 = *p, *p2 = p1->next;

            while(p2 && p2->val == p1->val) { //              

                p2 = p2->next;

            }

            if(p2 != p1->next) {

                *p = p2;

            } else {

                p = &(p1->next);

            }

        }

        return head;

    }

};

좋은 웹페이지 즐겨찾기