題目
Given a sorted linked list, delete all duplicates such that each element appears only once.
For example,
Given 1->1->2, return 1->2.
Given 1->1->2->3->3, return 1->2->3.
刪除鏈表中重復的元素毁习，保證每個元素只出現(xiàn)一次丈氓。
解題思路
因為鏈表從小到大排序，當前元素的下一個元素只有兩種可能：
- 與當前元素相同（即，當前元素在鏈表中重復出現(xiàn)）
- 大于當前元素（即臣疑，當前元素為鏈表中的唯一元素）
根據(jù)上面的觀察瘾婿，檢查一個元素是否重復出現(xiàn)只需要和該元素的下一個元素進行比較即可。因此狭郑，我們需要兩個指針。第一個指針p指向當前元素汇在，第二個指針t永遠指向p的下一個元素翰萨。
比較t和p的值：
-
t和p不相等，那么意味著p為唯一元素糕殉。所以保留該元素亩鬼，然后將指針p移動到下一個元素 -
t和p相等殖告，那么意味著該元素重復出現(xiàn)。所以只保留一份該元素雳锋，刪除重復元素t黄绩。然后p仍指向當前元素，移動t到下一個元素玷过，繼續(xù)與p進行比較爽丹，重復以上步驟，直到t和p不相等
舉個例子：
一個鏈表：1->1->1->1->3->4
從頭循環(huán)該鏈表辛蚊，一次循環(huán)中完成以下步驟：
1. p = 1,
t = p->next 所以 t = 1
2. t == p?
比較t和p粤蝎，因為t,p相等，所以刪除t
注意袋马！刪除t之前初澎，我們要設置p->next = t->next，不然鏈表會斷掉
新的鏈表：1->1->1->3->4
3. 返回第一步...
因為t永遠是p的下一個元素飞蛹，只要t==p谤狡，那么重復的t都不會刪除直到t=3
代碼
/**
* 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) {
if(!head) {return NULL;}
ListNode *p = head, *t;
while(p != NULL) {
t = p->next;
if(t != NULL) {
if(p->val == t->val) { // 當前元素與下一個元素相同
p->next = t->next; // p的下一個元素為t的下一個元素
delete t; //刪除重復元素t
}else { // 當前元素與下一個元素不同，移動指針到下一個元素
p = p->next;
}
}else { // 當前元素為列表中最后一個元素
return head;
}
}
return head;
}
};
