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

/** * RECOMMENDED CONFIGURATION VARIABLES: EDIT AND UNCOMMENT THE SECTION BELOW TO INSERT DYNAMIC VALUES FROM YOUR PLATFORM OR CMS. * LEARN WHY DEFINING THESE VARIABLES IS IMPORTANT: https://disqus.com/admin/universalcode/#configuration-variables*/ /* var disqus_config = function () { this.page.url = PAGE_URL; // Replace PAGE_URL with your page's canonical URL variable this.page.identifier = PAGE_IDENTIFIER; // Replace PAGE_IDENTIFIER with your page's unique identifier variable }; */ (function() { // DON'T EDIT BELOW THIS LINE var d = document, s = d.createElement('script'); s.src = 'https://chenzz.disqus.com/embed.js'; s.setAttribute('data-timestamp', +new Date()); (d.head || d.body).appendChild(s); })();