LeetCode: Remove Duplicates from Sorted List II

题目

https://oj.leetcode.com/problems/remove-duplicates-from-sorted-list-ii/

分析

  1. 双指针来实现, 左侧的指针指向上一个有效结点, 右侧的指针进行试探, 直到找出有效结点后和左侧的指针连接起来。

  2. 由于链表第一个结点可能被删除掉, 所以左侧指针初始化为头结点的前一个指针。

代码

class Solution
{
public:
    ListNode *deleteDuplicates(ListNode *head)
    {
        if (head == NULL)
            return head;

        ListNode *pre_head = new ListNode(0);
        pre_head->next = head;

        ListNode *pl, *pr;
        pl = pre_head;
        pr = head;
        while (pr != NULL)
        {
            if (pr->next != NULL && pr->val == pr->next->val)
            {
                pl = pl->next;
                pr = pr->next;
            }
            else
            {
                while (pr->next != NULL && pr->val == pr->next->val)
                {
                    ListNode *temp = pr;
                    pr = pr->next;
                    delete temp;
                }
                pr = pr->next;
            }
        }

        ListNode *temp = pre_head;
        pre_head = pre_head->next;
        delete temp;
        return pre_head;
    }
};

参考

http://fisherlei.blogspot.com/2013/03/leetcode-remove-duplicates-from-sorted.html

本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/39544599