程序员经验分享-hwhale

【数据结构初阶】单链表OJ题

2023-10-27

⭐博客主页：️CS semi主页
⭐欢迎关注：点赞收藏+留言
⭐系列专栏：数据结构初阶
⭐代码仓库：Data Structure
家人们更新不易，你们的点赞和关注对我而言十分重要，友友们麻烦多多点赞＋关注，你们的支持是我创作最大的动力，欢迎友友们私信提问，家人们不要忘记点赞收藏＋关注哦！！！

单链表OJ题

一、移除链表元素

1、题目描述

在这里插入图片描述

2、解题思路

在这里插入图片描述
我们用三个指针，cur先记录头结点，prev为空指针，进去以后判断如果是头删则判断的是prev为NULL，我们很容易判断的，所以就是头删，头结点为cur->next，然后将原本的头结点释放即可。而如果不是头结点，我们可以利用指针移动的快慢将prev移动到cur的前一位，next就为cur->next，将prev与next进行连接，再将cur进行释放即可。

3、解题代码

if(head == NULL){
        return NULL;
    }
    struct ListNode* cur=head;
    struct ListNode* prev=NULL;
    while(cur){
        //如果当前结点是需要删除的结点
        if(val==cur->val){
            //保存一下下一个结点
            struct ListNode* next=cur->next;
            //如果删除的为头结点，更新头结点
            //否则让当前结点的前面一个结点链接next结点
            if(prev==NULL){
                head=cur->next;
            }
            else{
                prev->next = cur->next;
            }
            //释放当前节点，让cur指向next
            free(cur);
            cur=next;

        }
        else{
            prev=cur;
            cur=cur->next;
        }
    }
    return head;

二、反转链表

1、题目描述

在这里插入图片描述

2、解题思路

（1）三指针法

在这里插入图片描述
我们看图，利用三指针，第一个指针n1为头结点，第二个指针n2为头结点的next，第三个指针n3为头结点的next的next。我们先判断n2是不是空，这里为什么判断n2是因为我们想要将最后一个箭头反转过来的判断条件为n2刚好到空的时候，所以判断n2是否为空最为合适。我们每进行一步，将n2的指针指向反转，再利用迭代n1、n2和n3都往后移动一位，直到退出循环，返回新的头结点n1。

（2）头插法

在这里插入图片描述
定义一个头结点为cur，头结点的next为next，拿一个尾插到新链表，一直到cur为空即可，思路贼简单。

3、解题代码

（1）三指针法

// 三指针法
    if(head==NULL || head->next==NULL)
        return head;
    struct ListNode* n1, *n2, *n3=NULL;
    n1=head;
    n2=n1->next;
    n3=n2->next;
    n1->next=NULL;
    while(n2){
        //反转
        n2->next=n1;
        //迭代
        n1=n2;
        n2=n3;
        if(n3)
            n3=n3->next;
    } 
    return n1;

（2）头插法

struct ListNode* cur = head;
    struct ListNode* newhead = NULL;
    while(cur){
        struct ListNode* next=cur->next;
        cur->next=newhead;
        newhead=cur;
        cur=next;
    }
    return newhead;

三、链表的中间节点

1、题目描述

在这里插入图片描述

2、解题思路

利用快慢指针，慢指针走一步，快指针走两步。判断条件为快指针以及快指针的下一个结点任意一个为空即跳出循环，而我们写的是进入循环的条件，所以必须是快指针以及快指针的下一个结点两者都需要不为空才继续。

3、解题代码

ListNode* middleNode(ListNode* head) {
        struct ListNode* slow=head;
        struct ListNode* fast=head;
        while(fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }

四、链表中的倒数第k个结点

1、题目描述

在这里插入图片描述

2、解题思路

还是快慢指针进行解决问题，这次的快指针和慢指针的步频是一样的，只不过是快指针先走k步，然后慢指针再和快指针一起走，等到快指针为空的时候，慢指针就是我们要找的倒数第k个结点，返回慢指针即可。

3、解题代码

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

		while(fast!=nullptr){
			fast=fast->next;
			slow=slow->next;
		}
		return slow;
    }

五、合并链表

1、题目描述

在这里插入图片描述

2、解题思路

（1）无哨兵位头结点

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
无哨兵位的头结点解题相对来讲有点复杂，我们细细分析，我们将list1的头放到cur1上，将list2的头放到cur2上，然后创建一个新链表，判断如果头结点还没插入值，那么就将较小的先插入，如果有值，那就tail后面插入较小的值，一直到两个链表中的其中一个链表为空停止，而我们知道，有可能的情况是一个链表为空，另一个链表不为空，那么我们就将不为空的链表再在尾接上去即可。但其实看似没问题，那当然还是有bug的，倘若我们的cur1和cur2在刚开始就为空，那么循环是进不去的，这就需要我们在开头进行判断一下是否为空，一个为空，那么就将另一个直接返回。

（2）有哨兵位的头结点

在这里插入图片描述
在这里插入图片描述
思路那就更简单了，我们设立一个不存储任何有效数据的头结点guard，这样子就不需要判断头结点是否为空了，因为本来就存在头结点，链表不可能为空，其他与前一种一样，我们上代码看一下。

3、解题代码

（1）无哨兵位的头结点

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        //不带哨兵位
        if(list1==NULL)
            return list2;
        if(list2==NULL)
            return list1;

        ListNode* cur1=list1;
        ListNode* cur2=list2;
        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）有哨兵位的头结点

        //带哨兵位
        ListNode* cur1=list1;
        ListNode* cur2=list2;
        ListNode* guard=NULL,*tail=NULL;
        guard=tail=(ListNode*)malloc(sizeof(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!=NULL)
            tail->next=cur1;
        if(cur2!=NULL)
            tail->next=cur2;
        
        ListNode* next=guard->next;
        free(guard);
        return next;

六、链表分割

1、题目描述

在这里插入图片描述

2、解题思路

在这里插入图片描述
既然题目是链表的分割，那我们就设置一个长头和长尾（ltail和lhead）以及短头和短尾（shead和stail）。将小于x的指针放到短的，大于或者等于的值放到长的链表中，最后短的tail指向长的head的next即可。

3、解题代码

class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
        // write code here
        // 分区域进行分装，小于的数放在前一个链表，大于的数放在后一个链表
        ListNode* cur=pHead;
        ListNode* shead,*stail,*lhead,*ltail;
        shead=stail=(ListNode* )malloc(sizeof(ListNode));
        lhead=ltail=(ListNode* )malloc(sizeof(ListNode));
        stail->next=NULL;
        ltail->next=NULL;
        while(cur)
        {
            if(cur->val<x)
            {
                stail->next=cur;
                stail=cur;
            }
            else
            {
                ltail->next=cur;
                ltail=cur;
            }

            cur=cur->next;
        }
        stail->next=lhead->next;
        ltail->next=NULL;
        ListNode* p=shead->next;
        // free(shead);
        // free(stail);
        // free(lhead);
        // free(ltail);
        return p;

    }
};

七、链表的回文

1、题目描述

在这里插入图片描述

2、解题思路

在这里插入图片描述
先找到中间结点，再从中间结点开始，对后半段逆置，前半段的数据和后半段的数据比较就可以了，如果相等则为回文，不是就不是回文。这边我们用到前面的找中间结点和逆置的函数。

3、解题代码

class PalindromeList {
  public:
    struct ListNode* middleNode(struct ListNode* head) {
        struct ListNode* slow = head;
        struct ListNode* 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;
    }

        bool chkPalindrome(ListNode * head) {
            ListNode* mid = middleNode(head);
            ListNode* rhead = reverseList(mid);
            while(head&&rhead){
                if(head->val != rhead->val){
                    return false;
                }
                head=head->next;
                rhead=rhead->next;
            }
            return true;
        }
    };

八、相交链表

1、题目描述

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

2、解题思路

在这里插入图片描述
思路很清奇，但也很常规，这道题可以运用将A链表内所有的数依次与B链表中的值进行比较地址即可，但我们想要提升提升，那就在空间复杂度为O(1)，时间复杂度为O(N)的条件下进行判断链表是否相交。这需要用到快慢指针，先是算算两条链表的长度，计算出差值，让快指针先走差值，这样子不就是快慢指针在同一平台上了吗，那就快指针和慢指针一起走，直到遇到相交点（地址相同点），返回结点即可，遇不到那就返回空，但这其中蕴含的条件是如果相交，两条链表的尾结点是肯定地址一样的，因为不可能有相交后再分开的情况。

3、解题代码

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        //分别求两个链表的长度
        //长的链表先走差距步
        //再同时走，第一个地址相同的就为交点
        ListNode* tail1 = headA;
        ListNode* tail2 = headB;
        int count1 = 1;
        int count2 = 1;
        while(tail1->next){
            tail1=tail1->next;
            count1++;
        }
        while(tail2->next){
            tail2=tail2->next;
            count2++;
        }

        int gap = abs(count1 - count2);
        
        ListNode* longlist = headA, *shortlist = headB;

        if(count1 < count2){
            longlist = headB;
            shortlist = headA;
        }

        if(tail1 != tail2){
            return NULL;
        }

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

        while(longlist!=shortlist){
            longlist=longlist->next;
            shortlist=shortlist->next;
        }
        
        return longlist;
    }
};

九、环形链表（详细描述）

1、题目描述

在这里插入图片描述
在这里插入图片描述

2、解题思路

在这里插入图片描述

思路很简单，只需要用快慢指针即可，快指针的步伐是慢指针的两倍步数，两者只要相等即为相遇，两者找不到相等的地址则为不相遇，那就是没有环。

3、解题代码

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

4、为何这么做？

（1）小问题1

1、为什么slow走一步，fast走两步，它们会不会相遇？会不会错过？请证明：
在这里插入图片描述
在这里插入图片描述

（2）小问题2

2、当slow走一步，fast走三步，它们会不会相遇？
在这里插入图片描述
答案居然是不一定！！！终究是错付了。

（3）结论

看距离的大小，如果距离为1，则肯定能追到，如果为其他则需要分情况讨论，有可能永远追不到。

十、环形链表 II

1、题目描述

在这里插入图片描述
在这里插入图片描述

2、解题思路

（1）入口点相遇

在这里插入图片描述
结论：一个指针从相遇点走，一个指针从起始点走，会在入口点相遇。

（2）求交点

在这里插入图片描述
我们可以转化成为求交点的问题，将相遇点的下一个结点定义为lt1，将起始点定义为lt2，然后两个指针同时走，直到相遇，至于如何相遇的，我们在相交链表中提及到了，长的链表先走差距步，再两个链表同时走，直到在入口点相遇，返回入口点的指针。
在这里插入图片描述

3、解题代码

（1）入口点相遇

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode* fast, *slow;
        fast = slow = head;
        while(fast && fast->next){
            slow = slow->next;
            fast = fast->next->next;

            if(slow == fast){
                ListNode* meet = slow;
                ListNode* start = head;

                while(meet != start){
                    meet = meet->next;
                    start = start->next;
                }
                return meet;
            }
        }
        return NULL;
    }
};

（2）求交点

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        //分别求两个链表的长度
        //长的链表先走差距步
        //再同时走，第一个地址相同的就为交点
        ListNode* tail1 = headA;
        ListNode* tail2 = headB;
        int count1 = 1;
        int count2 = 1;
        while(tail1->next){
            tail1=tail1->next;
            count1++;
        }
        while(tail2->next){
            tail2=tail2->next;
            count2++;
        }

        int gap = abs(count1 - count2);
        
        ListNode* longlist = headA, *shortlist = headB;

        if(count1 < count2){
            longlist = headB;
            shortlist = headA;
        }

        if(tail1 != tail2){
            return NULL;
        }

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

        while(longlist!=shortlist){
            longlist=longlist->next;
            shortlist=shortlist->next;
        }
        
        return longlist;
    }

    ListNode *detectCycle(ListNode *head) {
        ListNode* fast, *slow;
        fast = slow = head;
        while(fast && fast->next){
            slow = slow->next;
            fast = fast->next->next;

            if(slow == fast){
                ListNode* meet = slow;
                ListNode* lt1 = meet->next;
                ListNode* lt2 = head;
                meet->next=NULL;
                return getIntersectionNode(lt1, lt2);
            }
        }
        return NULL;
    }
};

十一、复制带随机指针的链表

1、题目描述

在这里插入图片描述
在这里插入图片描述
这道题目看起来非常的难懂，看题目来讲是在是太难理解了，那我们就简单翻译一下这道题目吧！这到题目就是定义一个结构体链表，存数据、next和random（随机指针），随机指针指向的位置不确定，但指向的是第几个数，就我们看实例1中的13指向的是第0个链表节点，那么就是[13,0]，那我们最后依次输出指向不同的结点。

2、解题思路

这道题的解题思路很清奇，先是需要我们在每个结点的后面插入一个相同数据的copy结点，然后再链接，之后便将复制的结点的random指向原本结点的random即可，形成一种新的链接关系，之后再将新的结点尾插到新的链表中即可，将原本被破坏的链表恢复，再返回新链表的头即可。
在这里插入图片描述

3、解题代码

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;
}

总结

单链表的OJ题有些难度很大，有些难度不大，但发现思路都是很新奇的，不和以前的数组那样思路是遍历二分这种的，在链表的练习中是有很多不一样的思路在里面的。

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

数据结构初阶

链表

数据结构

算法

【数据结构初阶】单链表OJ题 的相关文章

随机推荐

  • Mybatis typealiaspackage 通配符扫描方法

    最近两天项目需求研究了一下mybatis拦截器 对于Mybatis拦截器发现其功能强大 虽很灵活但是其内部对象转换太麻烦很多接口没有完全暴露出来 甚至不得不通过反射的方式去取其内部关联对象 可能Mybatis也不希望用户直接对其内部Stat

  • 服务器上数据盘不显示,云服务器不显示数据盘

    云服务器不显示数据盘 内容精选 换一换 当卸载数据盘时 支持离线或者在线卸载 即可在挂载该数据盘的云服务器处于 关机 或 运行中 状态进行卸载 弹性云服务器在线卸载磁盘 详细信息请参见在线卸载磁盘 裸金属服务器当前支持将SCSI类型磁盘挂载

  • 169.多数元素 C++

    ans1 先对数组排序 1 1 class Solution public int majorityElement vector

  • 前端web基础四：css简介

    1 什么是css css3 css的第三个版本 css是由很多模块构成 有些模块高于3或者低于3 但是现在w3c统一标准称为css3跟html5一样称html 一般我们说的css就是css3以后基本上不会改了 css 层叠样式表cascad

  • x264源码分析--dpb-size

    dpb size 参数含义 解码缓冲区大小 decode picture buffer 参数解析 OPT dpb size p gt i dpb size atoi value 代码逻辑 h gt param i dpb size x264

  • 面试官问 ： ArrayList 不是线程安全的，为什么 ？（看完这篇，以后反问面试官）

    前言 金三银四 也许 但是 近日 又收到金三银四一线作战小队成员反馈的战况 我不管你从哪里看的面经 但是我不允许你看到我这篇文章之后 还不清楚这个面试问题 本篇内容预告 ArrayList 是线程不安全的 为什么 结合代码去探一探所谓的不安

  • Mask Rcnn目标分割-训练自己数据集-详细步骤

    本文接着介绍了Mask Rcnn目标分割算法如何训练自己数据集 对训练所需的文件以及训练代码进行详细的说明 本文详细介绍在只有样本图片数据时 如果建立Mask Rcnn目标分割训练数据集的步骤 过程中用到的所有代码均已提供 一 制作自己的数

  • 严重性代码说明项目文件行 禁止显示状态错误 C4996 fopen（'fscanf'、strcmp）：This function or variable may be unsafe. 最全解决办法

    解决fopen fscanf 在VS中要求替换为fopen s fscanf s的最全解决办法 ps 在使用MFC中遇到上述问题 可以通过方法三解决方法一 在程序最前面加 define CRT SECURE NO DEPRECATE 方法二

  • k8s中通过ingress暴露多端口deployment

    前言 项目中有一个notify微服务 业务逻辑上 需要在web界面上操作发送模板 微服务 和推送 websocket 因此需要将后端的微服务和websocket同时对外暴露 前端web界面操作时需要走外网 同时实现微服务内部之间和notif

  • 树莓派4B使用串口登录的设置方法

    特别提示 本文具有时效性 当前我使用的是pi4硬件 镜像版本 raspberrypi 5 15 61 32位 在我解决该问题的时候 在网上查找了很多方法 有些方法被实际测试发现是不行的 所以 请注意随时间的推移有可能我的这些解决方法并不一定

  • 配置可视化docker+ROS环境

    一直以来 我以为docker是没有图形界面的 我就用它做过编译服务 构建编译环境 时隔多年 再次用到 它居然支持了 1 docker图形界面配置 主机端运行命令 xhost 使能宿主机接收其他客户端的显示需求 docker端配置显示参数 e

  • 推荐系统(3)---寻找数据集中的相似用户

    寻找数据集中的相似用户 coding utf 8 寻找数据集中的相似用户 import json import numpy as np 计算user1 和 user2的相关系数 def pearson score dataset user1

  • Leetcode 150.逆波兰表达式求值（以及字符串比较时遇到的问题）

    题目 根据 逆波兰表示法 求表达式的值 有效的算符包括 每个运算对象可以是整数 也可以是另一个逆波兰表达式 注意 两个整数之间的除法只保留整数部分 可以保证给定的逆波兰表达式总是有效的 换句话说 表达式总会得出有效数值且不存在除数为 0 的

  • ThreadPoolTaskScheduler实现动态管理定时任务

    最近 有个项目有需要用到定时任务 所以做了一个动态管理定时任务的模块 本文将从项目背景 需求 选型 思路 具体实现等方面展开介绍 背景 有个支付类的项目 中间会产生一些中间态的订单 需要有个定时任务轮询确认订单状态 该类项目体量较小 单节点

  • [数据库] SQL语句select简单记录总结

    最近SQL语句写得比较多 也发现了自己的很多不足之处 在此先写一篇关于SQL语句的在线笔记 方便大家学习和后面的工作 SQL Server MySQL Oracle基本语法都类似 接下来我需要阅读 SQL Server性能优化与管理的艺术

  • 【漏洞一】检测到目标URL存在http host头攻击漏洞

    漏洞 检测到目标URL存在http host头攻击漏洞 原因 在项目中使用了 request getServerName 导致漏洞的出现 不要使用request中的serverName 也就是说host header可能会在攻击时被篡改 依

  • 回归分析常数项t值没有显著异于零怎么办_一文详解经典回归分析

    在如今机器学习 数据科学 人工智能热潮下 回归分析似乎成了家喻户晓的东西 实际上回归分析自Galton爵士提出以及Pearson和Fisher的理论的加持 经过一百多年的发展 早已成了发现客观规律的有力武器 回归分析的文章已经多得数不胜数了

  • Go语言中的函数字面量与匿名函数

    写在前面 习惯性的在写内容前说点儿什么 个人感觉Go语言中的函数字面量这个东西用着不是很顺手 所以想着总结一下 今天先从简单的开始 持续更新 给出概念 命名函数的作用范围是包级别的 这个大家都知道 如果想在程序的任意表达式中使用一个变量来表

  • 小谈移动端加密

    加密方式大致分为以下几种 哈希 散列函数 MD5 SHA1 SHA256 512 对称加密算法 DES 3DES AES 高级密码标准 美国国家安全局使用的加密算法 非对称加密算法 RSA 很多项目中都用到了MD5 它是一种不可逆算法 相同

  • 【数据结构初阶】单链表OJ题

    博客主页 CS semi主页 欢迎关注 点赞收藏 留言 系列专栏 数据结构初阶 代码仓库 Data Structure 家人们更新不易 你们的点赞和关注对我而言十分重要 友友们麻烦多多点赞 关注 你们的支持是我创作最大的动力 欢迎友友们私信

热门标签