[LeetCode]Remove Duplicates from Sorted List

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.

这道题是要求删除有序单链表中的重复元素，比如，一段连续N个1，，删除N-1个1。

思路很简单，直接遍历单链表，设两个指针p,q，初始时p指向head,q指向head->next 1. 若p和q所指结点的值不等，则同时后移 2. 若相等，则p不移动，q后移，直到q的后继结点的值不等于p结点的值。保存q的后继结点。 3. 将p的next指向q的后继结点，依次删除p->next到q之间所有的结点。并将q指向q的后继结点。 4. 重复上述步骤，直到遍历结束。

需要注意边界情况，比如空链表等。

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

学习会使你永远立于不败之地。