题目
在一个排序的链表中,存在重复的结点,请删除该链表中重复的结点,重复的结点不保留。
样例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;}};
