[LeetCode]Remove Duplicates from Sorted List II

I的变体，稍微麻烦一点。但是思想还是双指针，因为这道题目当中head是可能会被删掉的，所以我们需要用一个helper node来keep track of新的head节点。指针1一直停在左边已经remove duplicates的链表的末尾，指针2和指针3来检测剩余linkedlist是否有大于等于2个相同的数，然后根据情况是决定保留删除即可。时间复杂度O(N)，常数空间。代码如下：

	/**
	* Definition for singly-linked list.
	* struct ListNode {
	* int val;
	* ListNode *next;
	* ListNode(int x) : val(x), next(NULL) {}
	* };
	*/
	class Solution {
	public:
	ListNode* deleteDuplicates(ListNode* head) {
	ListNode* helper = new ListNode(-1);
	helper->next = head;
	auto prev = helper, curr = head;
	while(curr)
	{
	auto next = curr;
	while(next && next->val == curr->val)
	next = next->next;
	if(curr->next == next)
	{
	prev = prev->next;
	curr = curr->next;
	}
	else
	{
	prev->next = next;
	curr = next;
	}
	}
	return helper->next;
	}
	};

view raw Remove Duplicates from Sorted List II.cpp hosted with ❤ by GitHub