题目
在一个排序的链表中,存在重复的结点,请删除该链表中重复的结点,重复的结点不保留。
样例1
输入:1->2->3->3->4->4->5
输出:1->2->5
样例2
输入:1->1->1->2->3
输出:2->3
解法:双指针
先准备一个头结点指向头指针,减少特判
然后准备两个指针,p在后,q在前
由于是完全删除重复的结点,因此p必须指向重复段的前一个结点,q必须指向重复段的下一个结点,根据p和q之间的距离来判断,如果中间只有一个结点,那么肯定是保留,否则p直接指向q
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* deleteDuplication(ListNode* head) {
auto h = new ListNode(-1);
h->next = head;
auto p = h;
while (p->next) {
auto q = p->next;
while (q && q->val == p->next->val) {
q = q->next;
}
if (q == p->next->next) p = p->next;
else p->next = q;
}
return h->next;
}
};