LeetCode82——Remove Duplicates from Sorted List II

比眉伴天荒 2022-08-20 03:15 4阅读 0赞

# LeetCode82——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.

意思就是删除链表中重复的元素，只要重复，就一个不留。

--------------------

## 分析 ##

这题让一开最困惑的就是因为在leetcode的链表题里面，都是默认头结点=头指针，也就是意味着，如果出现类似  
`1->1->2`这种的就感觉很麻烦。

于是想个办法，构造一个头结点start，让并令`start->next=head`，这样操作起来就不那么膈应了，只需要按照以往的思路对链表进行删除操作就OK。

--------------------

## 代码 ##

class Solution {
    public:
        ListNode* deleteDuplicates(ListNode* head) {
            ListNode *start = new ListNode(0);
            start->next = head;
            ListNode * p = start->next;
            ListNode *q = start;
            while (NULL != p&&NULL != p->next)
            {
                if (NULL != p->next&&p->next->val == p->val)
                {
                    while (NULL != p->next&&p->next->val == p->val)
                    {
                        ListNode* r = p;
                        p = p->next;
                        delete r;
                    }
                    ListNode*r = p;
                    q->next = r->next;
                    p = r->next;
                    delete r;
                }
                else
                {
                    p = p->next;
                    q = q->next;
                }
            }
            return start->next;
        }
    };