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

  1. /**
  2. * Definition for singly-linked list.
  3. * struct ListNode {
  4. * int val;
  5. * ListNode *next;
  6. * ListNode(int x) : val(x), next(NULL) {}
  7. * };
  8. */
  9. class Solution {
  10. public:
  11. ListNode* deleteDuplication(ListNode* head) {
  12. auto h = new ListNode(-1);
  13. h->next = head;
  14. auto p = h;
  15. while (p->next) {
  16. auto q = p->next;
  17. while (q && q->val == p->next->val) {
  18. q = q->next;
  19. }
  20. if (q == p->next->next) p = p->next;
  21. else p->next = q;
  22. }
  23. return h->next;
  24. }
  25. };