• 力扣(LeetCode)82. 删除排序链表中的重复元素 II(C语言)


    双指针

    声明哑结点,便于操作头结点。声明左指针 p p p p p p 指向可能删除结点的前一个位置。 声明右指针 q q q q = p − > n e x t − > n e x t q=p->next->next q=p>next>next p / q p/q p/q 之间隔着一个结点,便于删除操作。当 q q q 非空,判断 p − > n e x t p->next p>next q q q 的结点值是否相等,将 q q q 移动到与 p − > n e x t p->next p>next 结点值不相等的位置。此时 q q q 没有移动,说明 q q q 和前一结点值不相等,使 p p p 后移即可 ; q q q 移动了,说明 q q q 的前一段有相等的结点,使 p − > n e x t = q p->next=q p>next=q 即可。

    极简 C++
    class Solution {
    public:
        ListNode* deleteDuplicates(ListNode* head) {
            auto dummy = new ListNode(-1);
            dummy->next = head;
            auto p = dummy ;
            while(p->next){
                auto q = p->next->next;
                while(q&&q->val==p->next->val) q = q->next;
                if(p->next->next==q) p = p->next;
                else p->next = q;
            }
            return dummy->next;
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15

    时间复杂度: O ( n ) O(n) O(n) n n n 是链表的长度,遍历链表的时间复杂度是 O ( n ) O(n) O(n)

    空间复杂度: O ( 1 ) O(1) O(1) ,只使用了常量级空间。

    调试 C
    • 分析题意,删除所有重复元素,如 [ 1 , 1 ] [1,1] [1,1]删除后为 [ ] [ ] [],又如 [ 1 , 2 , 3 , 3 , 4 , 4 , 5 ] [1,2,3,3,4,4,5] [1,2,3,3,4,4,5],删除后为 [ 1 , 2 , 5 ] [1,2,5] [1,2,5]
    • 这种可能删除头结点的链表,我们通常使用一个哑结点 d u m m y H e a d dummyHead dummyHead指向头结点 h e a d head head,这样就不用判断头结点删除的特例条件了。
    • 这题还是有两个特例:
    1. 传入空结点。
    2. 传入单元素结点。
    • 上述特例不会有重复元素,直接返回头结点即可
    • 一开始,我们让 l e f t = d u m m y H e a d left=dummyHead left=dummyHead r i g h t = h e a d − > n e x t right=head->next right=head>next,此时 r i g h t right right领先 l e f t left left两个位置,在之后的遍历,遇到相同元素,就很方便删除 l e f t left left r i g h t right right之间的一个结点了。每次删除后,我们也保持 r i g h t right right l e f t left left的相对距离为 2 2 2
    • 删除完成后,我们返回 d u m m y H e a d − > n e x t dummyHead->next dummyHead>next,即为所求链表。
    //双指针, left right。
    //设置哑结点,方便第一个元素的删除。
    struct ListNode* deleteDuplicates(struct ListNode* head) {
        struct ListNode* dummyHead = (struct ListNode*)calloc(1, sizeof(struct ListNode));//声明哑结点
        dummyHead->next = head;
        struct ListNode* left = dummyHead;//左指针从哑结点出发。
        struct ListNode* right = head;//右指针从头结点出发。
        if (NULL == right || NULL == right->next) {//空链表和单元素链表,返回头结点即可
            return head;
        }
        right = right->next;//right领先left两个位置
        while (right) {//右指针非空
            int x = right->val;
            if (x == left->next->val) {//一旦删除结点,结点就不后移了。
                while (left->next&&left->next->val == x) {//left->next非空,right的val和right左一位的val相同
                    struct ListNode* temp = left->next;//待删除结点
                    left->next = right;//删除temp
                    temp->next = NULL;//避免野指针
                    free(temp);//释放被删除结点的空间
                    if(!right){//right为空
                        continue;//避免执行下一步,否则异常。
                    }
                    right = right->next;
                    continue;//检测新的left->next是否删除
                }
                continue;//在删除结点后,不能执行下一步,避免错过新的right。
            }
            left = left->next, right = right->next;//没有删除操作,左右指针右移一位。
        }
        return dummyHead->next;//哑结点目的,即是作为答案返回。
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31

    时间复杂度: O ( n ) O(n) O(n) n n n 是链表的长度,一次遍历链表的时间复杂度是 O ( n ) O(n) O(n)

    空间复杂度: O ( 1 ) O(1) O(1) ,只使用了常量级空间。

    致语
    • 理解思路很重要!
    • 欢迎读者在评论区留言,作为日更博主,看到就会回复的。
    AC

    AC

    AC

  • 相关阅读:
    【论文解读】The Power of Scale for Parameter-Efficient Prompt Tuning
    Vue脚手架学习笔记
    31 WEB漏洞-文件操作之文件包含漏洞全解
    Mysql查询今天到期、n天即将到期、还有n天过期相关sql
    NOSQL----redis的安装和基础命令
    使用html+css+js实现一个静态页面(含源码)
    Go 项目依赖注入wire工具最佳实践介绍与使用
    PHP遇见错误了看不懂?这些错误提示你必须搞懂
    精确率、召回率、F1值
    Springboot多数据源及事务实现方案
  • 原文地址:https://blog.csdn.net/Innocence02/article/details/127462270