题目描述

blablabla

样例

blablabla

算法

双指针，p指向左边保留段的结尾，q指向右边保留段的开始

* 注意while判断条件的顺序，先判断存在性，再判断值

while(q && (p->next->val == q->val)) q = q->next;

时间复杂度

参考文献

y总视频讲解

C++ 代码

/**
 * 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) {
        ListNode* dummy = new ListNode(-1);

        dummy -> next = head;
        ListNode* p = dummy;
        // p指向左边保留段的结尾
        while(p->next){
            ListNode* q = p->next;
            // q指向右边保留段的开始
            while(q && (p->next->val == q->val)) q = q->next;

            // 判断是否有重复数字
            if(p->next->next == q) p = p->next; // 无重复
            else p->next = q; // 有重复，则让p直接成为q的前一个节点
        }

        return dummy->next;
    }
};