[LeetCode]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.

这道题要求将单链表中的重复元素删去，与Remove Duplicates from Sorted List 稍有不同的是，，若有重复，则全部删除，不保留重复的第一个元素。

思路差不多，如下： 1. 为了便于操作，增设一个头结点pre，并设pre->next=head 2. 设两个指针p与q，初始时p指向pre的下一个结点。 3. 在p!=NULL的前提下，设q指向p的下一个结点。比较p与q所指结点的值是否相等，若不等，则二者同时后移； 4. 若相等，则将q后移直到q的下一个结点的值不等于p结点的值。 保留q的下一个结点r。将pre的next改为r，同时删除p到q之间的所有结点（包括p与q）。 5. 重复上述步骤直至链表结束。

写的时候注意边界情况即可。

/** * 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* p = head;ListNode* pre = new ListNode(0);pre->next = head;head = pre;if (p){ListNode* q = p->next;while (q){if (q->val > p->val){pre = p;p = q;q = q->next;}else{while (q->next&&q->next->val == p->val)q = q->next;ListNode* r = q->next;ListNode* h = p;int val = p->val;while (h&&h->val == val){ListNode* t = h;h = h->next;delete t;}pre->next = r;p = r;q = (p ? p->next : NULL);}}}return head->next;}};

一只小狗在沙漠中旅行，找到了电线杆，结果还是憋死了，