[toc]

题目介绍

题目链接

https://leetcode.com/problems/remove-duplicates-from-sorted-list/description/
题目考点

链表，递归，迭代
题目难度

LeetCode
题目大意

给出1个排好序的链表，删除其中的重复元素
输入

原链表
输出

删除重复元素后的链表

题解一

解题思路

递归法

首先通过遍历删除与头结点同值的结点，后面1部分的链表通过递归删除其中的重复结点，然后将当前头结点与后面1部分链表（已删除重复结点）连接起来，最终返回当前头结点。
复杂度分析

假设链表有n个结点，则时间复杂度和空间复杂度都为$O(n)$。

代码

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if (head==nullptr)
            return head;
        ListNode* cur=head;
        while(cur!=nullptr && cur->val == head->val)
            cur = cur->next;
        head->next = deleteDuplicates(cur);
        return head;
    }
};

题解二

解题思路

递归法

首先取出头结点，然后通过递归删除剩余链表中的重复结点并将其与头结点连接，然后判断当前头结点和第2个结点是否重复（如果重复则删除）。
复杂度分析

假设链表有n个结点，则时间复杂度和空间复杂度都为$O(n)$。

代码

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if (head==nullptr)
            return head;
        head->next = deleteDuplicates(head->next);

        if (head->next!=nullptr && head->val==head->next->val)
            return head->next;
        return head;
    }
};

题解三

解题思路

迭代法

整体思路为用哨兵sentry保存当前最后1个不重复结点，当发现新的不重复结点时将哨兵与该结点连接（这样就是一次性删除多个重复结点）。

具体方法为：遍历链表，当发现cur和sentry异值时则一次性删除多个重复结点并更新最后1个不重复结点为当前结点（sentry->next=cur;sentry=cur;），直到整个链表遍历结束。最后将最后1个不重复结点的下1个结点置空。
复杂度分析

假设链表长度为n，则时间复杂度为$O(n)$、空间复杂度为$O(1)$。

代码

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if (head==nullptr)
            return nullptr;
        ListNode* sentry=head, *cur=head;
        while(cur!=nullptr){
            if(sentry->val != cur->val){
                sentry->next = cur;
                sentry = cur;
            }
            cur = cur->next;
        }
        sentry->next=nullptr;
        return head;
    }
};

题解四

解题思路

迭代法

遍历链表，如果当前结点与下1个结点通知则删除下1个结点，否则更新下1个结点。

该思路与题解三的思路有相同也有不同，相同之处是都保存当前最后1个不重复结点，区别是题解三是一次性删除多个重复结点，而该方法是遇到1个重复结点则直接删除（1次删除1个结点）。
复杂度分析
- 假设链表长度为n，则时间复杂度为$O(n)$、空间复杂度为$O(1)$。

代码

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if (head==nullptr)
            return head;
        ListNode* cur=head, *next;
        while((next=cur->next)!=nullptr)
            if (cur->val==next->val)
                cur->next = next->next;
            else
                cur = next;
        return head;
    }
};

作者：@臭咸鱼

转载请注明出处：https://www.cnblogs.com/chouxianyu/

欢迎讨论和交流!