Day86 | 灵神 | 前后指针 删除排序链表中的重复元素 删除排序链表中的重复元素II

83.删除排序链表中的重复元素

83. 删除排序链表中的重复元素 - 力扣（LeetCode）

思路：

就是一道easy题目，思路并不难想，笔者是用两个指针，一个l一个r，他们之间相隔1，然后如果两个的值相等就把r所指向的节点给删了，然后更新r为r的下一个结点。如果值不相等，那自然一起往后走

也可以和灵神一样用一个指针，代码更简洁，但是我感觉两根指针可以把要做的事情想得更清楚一点？

完整代码：

/*
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {    
        if(head==nullptr)
            return head;
        ListNode* l=head;
        ListNode* r=head->next;
        while(r)
        {
            if(r->val==l->val)
            {
                ListNode* p=r->next;
                l->next=p;
                r=p;
            }
            else
            {
                l=l->next;
                r=r->next;
            }
        }
        return head;
    }
};*/

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if (head == nullptr) 
            return nullptr;
        ListNode* cur = head;
        while (cur->next) // 看看下个节点……
            if (cur->next->val == cur->val)  // 和我一样，删！
                cur->next = cur->next->next;
            else 
             // 和我不一样，移动到下个节点
                cur = cur->next;
        return head;
    }
};

82.删除排序链表中的重复元素II

82. 删除排序链表中的重复元素 II - 力扣（LeetCode）

思路：

和上一题一样，只是这道题要删除所有的相同元素，一个也不留下，所以l就指向相同部分的前一个结点，方便删除和删除之后连接链表

然后对相同的部分使用上一题的代码（用灵神的），即比较r和r->next的值然后进行删除。然后就把相同的部分删除的只剩下一个节点了，然后利用l再把剩下的那个结点给删了，然后更新r

这么说可能有点抽象，举个例子

链表[1,2,3,3,3,3,3,3,3,3,4,4,5]

1.我们遍历到l=2，r=第一个3的时候，发现有重复元素了

2.进行循环删除，删除后的数组为[1,2,3,4,4,5]，此时l=2，r=3

3.更新l，利用l把3给删了，这样就把所有的重复元素都给删除了

4.更新r让r指向3的下一个节点4

5.此时数组为 [1,2,4,4,5]，l=2，r=4

重复上述过程即可

完整代码：

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        ListNode *t=new ListNode;
        t->next=head;
        ListNode *l=t;
        ListNode *r=head;
        while(r&&r->next)
        {
            if(r->val==r->next->val)
            {
                while(r->next&&r->val==r->next->val)
                    r->next=r->next->next;
                l->next=l->next->next;
                r=r->next;
            }
            else
            {
                l=l->next;
                r=r->next;
            }
        }
        return t->next;
    }
};

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        ListNode dummy(0, head);
        auto cur = &dummy;
        while (cur->next && cur->next->next) {
            int val = cur->next->val;
            if (cur->next->next->val == val) { // 后两个节点值相同
                // 值等于 val 的节点全部删除
                while (cur->next && cur->next->val == val) {
                    cur->next = cur->next->next;
                }
            } else {
                cur = cur->next;
            }
        }
        return dummy.next;
    }
};