LeetCode83——Remove Duplicates from Sorted List

爱被打了一巴掌 2022-08-20 03:22 16阅读 0赞

# LeetCode83——Remove Duplicates from Sorted List #

与[LeetCode82——Remove Duplicates from Sorted List II][LeetCode82_Remove Duplicates from Sorted List II]类似，不删重，也就是说如果有重复的元素，保留一个。

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

## 原题 ##

> Given a sorted linked list, delete all duplicates such that each element appear only once.
> 
> For example,  
> Given 1->1->2, return 1->2.  
> Given 1->1->2->3->3, return 1->2->3.

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

## 分析 ##

就跟上一题类似了，依然构造头指针，不同的是，我们在进行重复元素的循环判断并删除的时候，保留一个即可。

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

## 代码 ##

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&&p->next != NULL)
            {
                if (p->next != NULL&&p->next->val == p->val)
                {
                    while (p->next != NULL&&p->next->val == p->val)
                    {
                        ListNode * r = p;
                        p = p->next;
                        delete r;
                    }
                    q->next = p;//保留一个元素
                    q=q->next;//始终让q位于可行链表的最后一个位置
                    p = p->next;
                }
                else
                {
                    p = p->next;
                    q = q->next;
                }
            }
            return start->next;
        }
    };

[LeetCode82_Remove Duplicates from Sorted List II]: http://blog.csdn.net/zhangxiao93/article/details/50592919