【数据结构刷题集】链表经典习题

😽 PREFACE
🎁欢迎各位→点赞 👍 + 收藏 ⭐ + 评论 📝
📢系列专栏: 数据结构刷题集
🔊本专栏涉及到题目是数据结构专栏的补充与应用,只更新相关题目,旨在帮助提高代码熟练度
💪 种一棵树最好是十年前其次是现在

移除链表元素

题目链接:https://leetcode.cn/problems/remove-linked-list-elements/description/

struct ListNode* removeElements(struct ListNode* head, int val){
    struct ListNode* prev=NULL,*cur=head;
    while(cur)
    {
        if(cur->val==val)
        {
            prev->next=cur->next;
            free(cur);
            cur=prev->next;
        }
        else
        {
            prev=cur;
            cur=cur->next;
        }
    }
    return head;
}

提交一下,我们会发现执行出错。

正确代码:

struct ListNode* removeElements(struct ListNode* head, int val){
    struct ListNode* prev=NULL,*cur=head;
    while(cur)
    {
        if(cur->val==val)
        {
            if(cur==head)
            {
                //头删
                head=cur->next;
                free(cur);
                cur=head;
            }
            else
            {
                prev->next=cur->next;
                free(cur);
                cur=prev->next;
            }  
        }
        else
        {
            prev=cur;
            cur=cur->next;
        }
    }
    return head;
}

链表的中间结点

题目链接:https://leetcode.cn/problems/middle-of-the-linked-list/description/

正确代码:

//尺取法
struct ListNode* middleNode(struct ListNode* head){
    struct ListNode* slow=head,*fast=head;
    while(fast&&fast->next)
    {
        slow=slow->next;
        fast=fast->next->next;
    }
    return slow;
}

链表中倒数第k个结点

题目链接:https://www.nowcoder.com/practice/529d3ae5a407492994ad2a246518148a?tpId=13&&tqId=11167&rp=2&ru=/activity/oj&qru=/ta/coding-interviews/question-ranking

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
    struct ListNode* fast=pListHead,*slow=pListHead;
    while(k--)
    {
        fast=fast->next;
    }
    while(fast)
    {
        slow=slow->next;
        fast=fast->next;
    }
    return  slow;;
}

结果代码运行不过:

正确代码:

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
    struct ListNode* fast=pListHead,*slow=pListHead;
    while(k--)
    {
        if(fast==NULL)//防止越界
        {
            return NULL;
        }
        fast=fast->next;
    }
    while(fast)
    {
        slow=slow->next;
        fast=fast->next;
    }
    return  slow;;
}

反转链表

题目链接:https://leetcode.cn/problems/reverse-linked-list/description/

法一:画图+迭代

//画图+迭代
struct ListNode* reverseList(struct ListNode* head){
    struct ListNode* prev,*cur,*next;
    prev=NULL,cur=head,next=head->next;
    while(cur)
    {
        //反转
        cur->next=prev;
        //迭代
        prev=cur;
        cur=next;
        next=next->next;
    }
    return prev;
}

这个只是最基本的逻辑,一运行发现还是过不了

//画图+迭代
struct ListNode* reverseList(struct ListNode* head){
    struct ListNode* prev,*cur,*next;
    prev=NULL,cur=head,next=head->next;
    while(cur)
    {
        //反转
        cur->next=prev;
        //迭代
        prev=cur;
        cur=next;
        if(next)
            next=next->next;
    }
    return prev;
}

再次提交,发现还是过不去:

正确代码1:

//画图+迭代
struct ListNode* reverseList(struct ListNode* head){
    if(head==NULL)
        return NULL;
    struct ListNode* prev,*cur,*next;
    prev=NULL,cur=head,next=head->next;
    while(cur)
    {
        //反转
        cur->next=prev;
        //迭代
        prev=cur;
        cur=next;
        if(next)
            next=next->next;
    }
    return prev;
}

法二:头插

为什么能想到头插呢?因为头插的顺序与链表的顺序刚好相反。

正确代码2:

//头插
struct ListNode* reverseList(struct ListNode* head){
    struct ListNode* cur=head, *newhead=NULL;
    while(cur)
    {
        struct ListNode* next=cur->next;
        //头插
        cur->next=newhead;
        newhead=cur;

        cur=next;
    }
    return newhead;
}

合并两个有序链表

题目链接:https://leetcode.cn/problems/merge-two-sorted-lists/description/

法一:不带哨兵位头结点

//不带哨兵位头结点
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
    struct ListNode* cur1=list1,*cur2=list2;
    struct ListNode* head=NULL,*tail=NULL;
    while(cur1&&cur2)
    {
        if(cur1->val<cur2->val)
        {
            if(head==NULL)
            {
                head=tail=cur1;
            }
            else
            {
                tail->next=cur1;
                tail=tail->next;
            }
            cur1=cur1->next;
        }
        else
        {
            if(head==NULL)
            {
                head=tail=cur2;
            }
            else
            {
                tail->next=cur2;
                tail=tail->next;
            }
            cur2=cur2->next;
        }
    }
    if(cur1)
    {
        tail->next=cur1;
    }
    if(cur2)
    {
        tail->next=cur2;
    }
    return head;
}

正确代码1:

//不带哨兵位头结点
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
    //如果链表为空,返回另一个
    if(list1==NULL)
    {
        return list2;
    }
    if(list2==NULL)
    {
        return list1;
    }
    struct ListNode* cur1=list1,*cur2=list2;
    struct ListNode* head=NULL,*tail=NULL;
    while(cur1&&cur2)
    {
        if(cur1->val<cur2->val)
        {
            if(head==NULL)
            {
                head=tail=cur1;
            }
            else
            {
                tail->next=cur1;
                tail=tail->next;
            }
            cur1=cur1->next;
        }
        else
        {
            if(head==NULL)
            {
                head=tail=cur2;
            }
            else
            {
                tail->next=cur2;
                tail=tail->next;
            }
            cur2=cur2->next;
        }
    }
    if(cur1)
    {
        tail->next=cur1;
    }
    if(cur2)
    {
        tail->next=cur2;
    }
    return head;
}

法二:带哨兵位头结点

正确代码2:

//带哨兵位头结点
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
    struct ListNode* cur1=list1,*cur2=list2;
    struct ListNode* guard=NULL,*tail=NULL;
    guard=tail=(struct ListNode*)malloc(sizeof(struct ListNode));
    tail->next=NULL;
    while(cur1&&cur2)
    {
        if(cur1->val<cur2->val)
        {
            tail->next=cur1;
            tail=tail->next;
            cur1=cur1->next;
        }
        else
        {
            tail->next=cur2;
            tail=tail->next;
            cur2=cur2->next;
        }
    }
    if(cur1)
    {
        tail->next=cur1;
    }
    if(cur2)
    {
        tail->next=cur2;
    }
    struct ListNode* head=guard->next;//防止内存泄漏
    free(guard);
    return head;
}

链表分割

题目链接:https://www.nowcoder.com/practice/0e27e0b064de4eacac178676ef9c9d70?tpId=8&&tqId=11004&rp=2&ru=/activity/oj&qru=/ta/cracking-the-coding-interview/question-ranking

class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
        struct ListNode* lessguard,*lesstail,*greaterguard,*greatertail;
        lessguard=lesstail=(struct ListNode*)malloc(sizeof(struct ListNode));
        greaterguard=greatertail=(struct ListNode*)malloc(sizeof(struct ListNode));
        lesstail->next=greatertail->next=NULL;

        struct ListNode* cur=pHead;
        while(cur)
        {
            if(cur->val<x)
            {
                lesstail->next=cur;
                lesstail=lesstail->next;
            }
            else
            {
                greatertail->next=cur;
                greatertail=greatertail->next;
            }
            cur=cur->next;
        }
        lesstail->next=greaterguard->next;

        pHead=lessguard->next;
        free(greaterguard);
        free(lessguard);
        return pHead;
    }
};

运行一下:

由于牛客不提供用例错误,我们可以转到力扣官网上查。当然了,也可以把我们写的用例往代码带,看看哪出错了。

正确代码:

class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
        struct ListNode* lessguard,*lesstail,*greaterguard,*greatertail;
        lessguard=lesstail=(struct ListNode*)malloc(sizeof(struct ListNode));
        greaterguard=greatertail=(struct ListNode*)malloc(sizeof(struct ListNode));
        lesstail->next=greatertail->next=NULL;

        struct ListNode* cur=pHead;
        while(cur)
        {
            if(cur->val<x)
            {
                lesstail->next=cur;
                lesstail=lesstail->next;
            }
            else
            {
                greatertail->next=cur;
                greatertail=greatertail->next;
            }
            cur=cur->next;
        }
        lesstail->next=greaterguard->next;
        greatertail->next=NULL;//不能忽略
        pHead=lessguard->next;
        free(greaterguard);
        free(lessguard);
        return pHead;
    }
};

链表的回文结构

题目链接:https://www.nowcoder.com/practice/d281619e4b3e4a60a2cc66ea32855bfa?tpId=49&&tqId=29370&rp=1&ru=/activity/oj&qru=/ta/2016test/question-ranking

正确代码:

//找中间节点
struct ListNode* middleNode(struct ListNode* head) {
    struct ListNode* slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}
//反转
struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode* cur = head;
    struct ListNode* newhead = NULL;
    while (cur) {
        struct ListNode* next = cur->next;
        //头插
        cur->next = newhead;
        //迭代
        newhead = cur;
        cur = next;
    }
    return newhead;
}

class PalindromeList {
  public:
    bool chkPalindrome(ListNode* A) {
        struct ListNode* mid=middleNode(A);
        struct ListNode* rHead=reverseList(mid);

        struct ListNode* curA=A;
        struct ListNode* curR=rHead;
        while(curA&&curR)
        {
            if(curA->val!=curR->val)
            {
                return false;
            }
            else
            {
                curA=curA->next;
                curR=curR->next;
            }
        }
        return  true;
    }
};

相交链表

题目链接:https://leetcode.cn/problems/intersection-of-two-linked-lists/description/

正确代码:

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    struct ListNode* tailA=headA,*tailB=headB;
    int lenA=0,lenB=0;
    while(tailA)
    {
        lenA++;
        tailA=tailA->next;
    }
    while(tailB)
    {
        lenB++;
        tailB=tailB->next;
    }

    //不相交的情况,不写的话leetcode也不会判错
    if(tailA!=tailB)
    {
        return NULL;
    }

    int gap=abs(lenA-lenB);
    struct ListNode* longList=headA,*shortList=headB;
    if(lenA<lenB)
    {
        longList=headB;
        shortList=headA;
    }

    while(gap--)
    {
        longList=longList->next;
    }

    while(longList!=shortList)
    {
        longList=longList->next;
        shortList=shortList->next;
    }
    return shortList;
}

环形链表

题目链接:https://leetcode.cn/problems/linked-list-cycle/description/

正确代码:

bool hasCycle(struct ListNode *head) {
    struct ListNode* slow=head,*fast=head;
    while(fast&&fast->next)
    {
        fast=fast->next->next;
        slow=slow->next;
        if(fast==slow)
        {
            return true;
        }
    }
    return false;
}

环形链表II

题目链接:https://leetcode.cn/problems/linked-list-cycle-ii/description/

法一:双指针

正确代码1:

struct ListNode *detectCycle(struct ListNode *head) {
    struct ListNode* slow=head,*fast=head;
    while(fast&&fast->next)
    {
        slow=slow->next;
        fast=fast->next->next;
        if(slow==fast)
        {
            //相遇
            struct ListNode* meetNode=slow;
            //公式
            while(meetNode!=head)
            {
                meetNode=meetNode->next;
                head=head->next;
            }
            return head;
        }
    }
    return NULL;
}

法二:转化成链表相交

正确代码2:

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    struct ListNode* tailA=headA,*tailB=headB;
    int lenA=0,lenB=0;
    while(tailA)
    {
        lenA++;
        tailA=tailA->next;
    }
    while(tailB)
    {
        lenB++;
        tailB=tailB->next;
    }

    //不相交的情况,不写的话leetcode也不会判错
    if(tailA!=tailB)
    {
        return NULL;
    }

    int gap=abs(lenA-lenB);
    struct ListNode* longList=headA,*shortList=headB;
    if(lenA<lenB)
    {
        longList=headB;
        shortList=headA;
    }

    while(gap--)
    {
        longList=longList->next;
    }

    while(longList!=shortList)
    {
        longList=longList->next;
        shortList=shortList->next;
    }
    return shortList;
}


struct ListNode *detectCycle(struct ListNode *head) {
    struct ListNode* slow=head,*fast=head;
    while(fast&&fast->next)
    {
        slow=slow->next;
        fast=fast->next->next;
        if(slow==fast)
        {
            struct ListNode* meetNode=slow;
            struct ListNode* list1=meetNode->next;
            struct ListNode* list2=head;
            meetNode->next=NULL;
            return getIntersectionNode(list1,list2);
        }
    }
    return NULL;
}

复制带随机指针的链表

题目链接:https://leetcode.cn/problems/copy-list-with-random-pointer/description/

正确代码:

struct Node* copyRandomList(struct Node* head) {
    //1.拷贝结点插入原结点的后面
    struct Node* cur=head;
    while(cur)//遍历整个链表
    {
        //插入
        struct Node* copy=(struct Node*)malloc(sizeof(struct Node));
        copy->val=cur->val;
        struct Node* next=cur->next;

        //cur copy next
        cur->next=copy;
        copy->next=next;

        cur=next;
    }
    //2.拷贝random结点
    cur=head;
    while(cur)
    {
        struct Node* copy=cur->next;
        if(cur->random==NULL)
        {
            copy->random=NULL;
        }
        else
        {
            copy->random=cur->random->next;
        }
        cur=cur->next->next;
    }
    //3.拆组
    struct Node* copyHead=NULL,*copyTail=NULL;
    cur=head;
    while(cur)
    {
        struct Node* copy=cur->next;
        struct Node* next=copy->next;

        //copy尾插
        if(copyHead==NULL)
        {
            copyHead=copyTail=copy;
        }
        else
        {
            copyTail->next=copy;
            copyTail=copyTail->next;
        }

        //恢复原链表
        cur->next=next;
        cur=next;
    }
    return copyHead;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.mfbz.cn/a/5753.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

第14章_视图

第14章_视图 &#x1f3e0;个人主页&#xff1a;shark-Gao &#x1f9d1;个人简介&#xff1a;大家好&#xff0c;我是shark-Gao&#xff0c;一个想要与大家共同进步的男人&#x1f609;&#x1f609; &#x1f389;目前状况&#xff1a;23届毕业生&#xff0c;目前在某公司…

Python 自动化指南(繁琐工作自动化)第二版:六、字符串操作

原文&#xff1a;https://automatetheboringstuff.com/2e/chapter6/ 文本是程序将处理的最常见的数据形式之一。您已经知道如何用操作符将两个字符串值连接在一起&#xff0c;但是您可以做得更多。您可以从字符串值中提取部分字符串&#xff0c;添加或删除空格&#xff0c;将字…

【新2023Q2模拟题JAVA】华为OD机试 - 找数字 or 找等值元素

最近更新的博客 华为od 2023 | 什么是华为od,od 薪资待遇,od机试题清单华为OD机试真题大全,用 Python 解华为机试题 | 机试宝典【华为OD机试】全流程解析+经验分享,题型分享,防作弊指南华为od机试,独家整理 已参加机试人员的实战技巧本篇题解:找数字 or 找等值元素 题目 …

华为OD机试 用java实现 -【重组字符串】

最近更新的博客 华为od 2023 | 什么是华为od,od 薪资待遇,od机试题清单华为OD机试真题大全,用 Python 解华为机试题 | 机试宝典【华为OD机试】全流程解析+经验分享,题型分享,防作弊指南华为od机试,独家整理 已参加机试人员的实战技巧本篇题解:重组字符串 题目 给定一个非…

计算机网络 第一章 概述小结

计算机网络 第一章 概述 1.1 因特网概述 名词解释&#xff1a;因特网服务提供者ISP&#xff08;Internet Service Provider&#xff09; 1.2 三种交换方式 电路交换&#xff1a; 优点&#xff1a;通信时延小、有序传输、没有冲突、适用范围广、实时性强、控制简单&#x…

【美赛】2023年MCM问题Y:理解二手帆船价格(代码思路)

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…

新导则下的防洪评价报告编制方法及洪水建模实践技术

目录 1、《防洪评价报告编制导则解读河道管理范围内建设项目编制导则》&#xff08;SL/T808- 2021&#xff09;解读 2、防洪评价相关制度与解析 3、防洪评价地形获取及常用计算 4、HEC-RAS软件原理及特点 5、HEC-RAS地形导入 6、一维数学模型计算 7、基于数学模型软件的…

用 云GPU 云服务器训练数据集--yolov5

目录 为何使用云GPU训练我们数据集&#xff1f; 云服务器训练数据集教程&#xff1a; 1.创建实例 2.上传数据&#xff08;OSS命令&#xff09; 以下是oss的操作过程 训练模型时可能出现的报错&#xff1a; 为何使用云GPU训练我们数据集&#xff1f; 我们总是花费长达十几个…

ISO文件内添加kickstart完成自动安装

目录 将待制作的centos iso文件挂载到/mnt/目录 将/mnt/下的所有文件复制到新的目录/tmp/mycentos 创建kickstart文件 修改启动文件 重新制作ISO文件 制作完成 kickstart可以实现根据配置自动安装操作系统&#xff0c;本文主要讲解如何让机器读取到iso文件后自动完成操作…

vue尚品汇商城项目-day02【11.对axios二次封装+12.接口统一管理】

文章目录11.对axios二次封装11.1为什么需要进行二次封装axios&#xff1f;11.2在项目当中经常有API文件夹【axios】12.接口统一管理12.1跨域问题12.2接口统一管理12.3不同请求方式的src/api/index.js说明本人其他相关文章链接11.对axios二次封装 安装命令&#xff1a;cnpm inst…

移动端滑动(touch)选项并实现多选效果

移动端滑动选项实现多选效果通过 touchstart、touchmove、 touchend、touchcancel 事件实现通过父元素代理事件的方式实现子组件点击选中选项如果选项添加 disabled 属性将不会被选中移动端拖拽 .box 和 .options 元素时&#xff0c;是有拖拽效果的&#xff0c;去除拖拽效果有两…

文件操作-C语言实现图片、压缩包等文件的“复制粘贴“过程

大部分参考自&#xff1a; 文件操作-C语言实现图片的“复制粘贴“过程_一个图像一部分复制到另一个图像中c语言_philippe coutinho的博客-CSDN博客 #define _CRT_SECURE_NO_WARNINGS的作用参考&#xff1a; https://mp.csdn.net/mp_blog/creation/editor/new/129414996 首先我们…

线程池的优点

线程池的优点&#x1f50e;优点1(降低资源消耗)&#x1f50e;优点2(提高响应速度)&#x1f50e;优点3(可管理性)&#x1f50e;结尾&#x1f50e;优点1(降低资源消耗) 有了线程池后,创建线程不再是向系统申请,而是从线程池中拿 当线程不再使用后,再还给线程池 线程的创建,虽然相…

47了解公有云平台 GCP 的基本服务和使用方法,包括 Compute Engine、Cloud Storage

GCP Compute Engine Google Cloud Platform (GCP) 的 Compute Engine 是一个可扩展的云计算平台&#xff0c;可以让您快速启动虚拟机实例来运行您的应用程序。它提供了一种灵活的方式来管理您的计算资源&#xff0c;并支持多种操作系统、应用程序框架和开发工具。以下是一些基本…

Leetcode.939 最小面积矩形

题目链接 Leetcode.939 最小面积矩形 Rating &#xff1a; 1752 题目描述 给定在 xy平面上的一组点&#xff0c;确定由这些点组成的矩形的最小面积&#xff0c;其中矩形的边平行于 x 轴和 y 轴。 如果没有任何矩形&#xff0c;就返回 0。 示例 1&#xff1a; 输入&#xff1…

centos7安装rabbitmq服务

centos7安装rabbitmq服务 第一 软件包准备 1.erlang依赖包 2.rabbitmq安装包 第二 安装rabbitmq 1.安装依赖 rpm -ivh erlang-21.3-1.el7.x86_64.rpmyum install socat -y2.安装rabbitmq服务 rpm -ivh rabbitmq-server-3.8.8-1.el7.noarch.rpm3.启动rabbitmq服务 system…

一次线上MySQL vCPU飙升引发的思考

vCPU飙升 在一个漆黑的深夜&#xff0c;MySQL丛库的vCPU在做一个三点任务的时候突然飙升&#xff0c;从MySQL面板中可以查到是以下查询导致的。 表数据及相关索引说明&#xff1a; hotel_info_tbl: 数据量&#xff1a;100w&#xff0c;id 为 primary keydynamic_cache_task_…

二项式反演

二项式反演 在很多情况下&#xff0c;“恰好”往往是不好求的&#xff0c;因为恰好意味着"≤\leq≤"并且"≥\geq≥"&#xff0c;需要进行很多限制&#xff0c;破坏了情况之间的独立性。 二项式反演则通过一定手段&#xff0c;使得限制"≤\leq≤&quo…

谷粒商城笔记+踩坑(21)——提交订单。原子性验令牌+锁定库存

目录 1、环境准备 1.1、业务流程 1.2、Controller 层编写下单功能接口 1.3、订单提交的模型类 1.4、前端页面 confirm.html 提供数据 2、提交订单业务完整代码 3、原子性验令牌&#xff1a;令牌的对比和删除保证原子性 4、初始化新订单&#xff0c;包含订单、订单项等信…

C++ : C++基础 :从内存的角度看 char[]和char*

char*和char[]区别1&#xff1a;数据在内存中的存储2&#xff1a;char*和 char[]分析3&#xff1a;char* p2 和 char p1[]3.1 修改指针所指向的地址4: string转char*5: char * 转string5.1 to_string()用法1&#xff1a;数据在内存中的存储 栈&#xff1a;就是在那些由编译器在…
最新文章