【数据结构】链表常见题目

文章目录

  • 链表
    • 合并两个有序链表
    • 反转链表
    • 复制带随机指针的链表
    • 环形链表
    • 环形链表II
    • 相交链表
    • 移除链表元素
    • 链表中倒数第k个节点
    • 链表分割
    • 链表的回文结构
    • 链表的中间节点
    • 旋转链表
    • 链表排序
    • 链表求和 (逆序求)
    • 链表求和II (正序求)
    • 重排链表
    • 奇偶链表
    • 反转链表II <==> 链表内指定区间反转
    • 删除链表中的节点
    • 删除有序链表当中重复的元素I
    • 删除有序链表当中重复的元素II
    • 合并K个升序链表
    • K个一组反转链表
    • 交换链表中的节点
    • 二进制链表转整数
    • 链表随机节点

链表

合并两个有序链表

https://leetcode.cn/problems/merge-two-sorted-lists/

1.定义一个哨兵位节点和一个tail节点标志尾节点

2.遍历两条有序链表,谁小就链接谁

3.最后还剩一条链表是没有遍历完成的,那么就让tail节点链接它

class Solution {
public:ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {//1.新建哨兵位节点ListNode* phead = new ListNode(-1);ListNode* tail = phead;//2.谁小就链接谁while(list1 && list2){if(list1->val > list2->val){tail->next = list2;tail = list2;list2 = list2->next;}else {tail->next = list1;tail = list1;list1 = list1->next;}}//3.判断谁还没有链接完if(list1) tail->next = list1;if(list2) tail->next = list2;return phead->next;}
};

反转链表

https://leetcode.cn/problems/reverse-linked-list/description/

prev:记录前一个节点 cur:当前遍历到的节点 next:保存cur的下一个节点

  • 先保存下一个节点 然后更改cur的指向,指向前一个节点
  • 然后迭代往后走
class Solution {
public:ListNode* reverseList(ListNode* head) {ListNode* prev = nullptr;//记录前一个节点ListNode* cur = head;//记录当前节点ListNode* next = nullptr;//记录下一个节点while(cur){next = cur->next;//先保存下一个节点cur->next = prev;//更改当前节点指向//prev cur next 迭代往后走prev = cur;cur = next;}return prev;}
};

复制带随机指针的链表

https://leetcode.cn/problems/copy-list-with-random-pointer/

1.在原链表节点之后拷贝一个节点

image-20230816094513759

2.处理拷贝节点的random指针

  • 注意:拷贝节点的random指针指向的节点是其原链表节点的random指针指向的节点的下一个节点
  • 坑点:有可能cur->random是空,也就是原来节点的random指针为空,那么当前拷贝节点的random指针也应该为空,否则cur->random->next 就会对空指针解引用!

image-20230816094637865

3.分离两条链表

  • 最好定义一个哨兵位节点和一个tail指针用于标记链接拷贝链表,
  • cur CopyCur next三者的关系重新处理

image-20230816094751726

class Solution {public:Node* copyRandomList(Node* head) {if(head == nullptr ) return nullptr;//1.在原节点后面copy一个节点Node* cur = head;while(cur){Node* copy = new Node(cur->val);//拷贝节点Node* next = cur->next;//cur copy next 链接cur->next = copy;copy->next = next;cur = next;//继续复制下一个节点}//2.处理拷贝节点的random指针cur = head;while(cur){Node* curCopy = cur->next;//cur的拷贝节点curCopy->random = cur->random == nullptr?nullptr:cur->random->next;cur = curCopy->next;}//3.拆离拷贝链表cur = head;Node* pnewHead = new Node(-1);//哨兵位Node* tail = pnewHead;while(cur){//cur copyCur next  Node* copyCur = cur->next;Node* next = copyCur->next;copyCur->next = nullptr;//让拷贝节点独立存在tail->next = copyCur;tail = tail->next;//重新处理链接关系,向后走cur->next = next;cur = next;}return pnewHead->next;}
};

环形链表

https://leetcode.cn/problems/linked-list-cycle/description/

方法:使用快慢指针,二者从头开始走,一个一次走两步,一个一次走一步,当二者相遇的时候,说明有环

class Solution {
public:bool hasCycle(ListNode *head) {//链表为空//注意:一个节点也能成环! 自己指向自己if(!head) return false;//快慢指针ListNode* fast = head;ListNode* slow = head;while(fast && fast->next){fast = fast->next->next;slow = slow->next;//二者相遇  注意:该条件不能放在上面!!!因为最初fast和slow都指向head,该条件应该放在下面if(slow == fast) return true;}return false;}
};

延申1:fast一次走两步,slow一次走一步,为什么一定能相遇?会不会在环里错过,永远遇不上

结论:slow一次走一步,fast一次走两步,如果存在环,slow和fast一定会在环内相遇

1.slow和fast,如果有环,一定是fast先进环,这时slow走了入环前距离的一半

2.随着slow进环,fast已经在环里面走了一段距离了(距离的多少跟环的大小有关)

  • 假设slow进环的时候,slow和fast的距离为N,fast开始追赶slow

3.slow一次走一步,fast一次走两步,二者的距离变化为:N N- 1 N -2 … 0,当二者的距离变为0的时候,就是相遇了

延申2:fast一次走n步(n>2),slow一次走一步,fast和slow能相遇吗

结论:fast一次走n步(n>2),slow一次走一步,不一定会相遇

  • 假设有环,fast一次走n步,slow一次走1步,fast和slow的距离不断减少n-1步

例子:假设fast一次走3步,如果slow进环之后,slow和fast的距离为N

如果N为偶数,那么二者之间的距离变化为:N N - 2 N - 4 … 2 0,此时二者相遇

如果N为计数,那么二者之间的距离变化为:N N - 2 N - 4 … 1 -1 ,二者距离变为-1,意味着fast超越了slow,此时fast和slow的距离为C -1 (假设C为环的大小)

  • 如果C - 1 为偶数,那么下一轮fast可以追上slow,二者相遇
  • 如果C - 1 为奇数,那么二者永远追不上

环形链表II

https://leetcode.cn/problems/linked-list-cycle-ii/description/

做法:

1.先看是否有环,快慢指针,fast一次走两步,slow一次走一步,如果存在环,fast和slow一定会相遇

2.假设相遇点为meetnode,一个指针从链表的头开始走,一个指针从相遇点开始走,二者一次走一步,当二者相遇的时候,该位置就是入环节点

image-20230816102819793

class Solution {
public:ListNode *detectCycle(ListNode *head) {if(!head) return nullptr;//快慢指针ListNode* fast = head;ListNode* slow = head;while(fast && fast->next){fast = fast->next->next;slow = slow->next;//二者相遇  注意:该条件不能放在上面!!!因为最初fast和slow都指向head,该条件应该放在下面if(slow == fast) {//分别从相遇点和链表头开始走,一次走一步  此时相遇就是入环位置ListNode* meet = slow;slow = head;while(slow != meet) {slow = slow->next;meet = meet->next;}return meet;}}return nullptr; //没有环}
};

相交链表

https://leetcode.cn/problems/intersection-of-two-linked-lists/description/

方法1:将A链表的所有节点放到容器当中(要放地址,不能放值),然后遍历B链表,看能否在容器当中找到该元素,如果找到,那么该节点就是相交节点

class Solution {
public://方法1:用容器保存其中一个链表的节点,然后遍历另外一个链表进行比对ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {multiset<ListNode*> s;ListNode* cur = headA;while(cur) {s.insert(cur);cur = cur->next;}cur = headB;while(cur){cout << cur->val << endl;if(s.find(cur) != s.end()) return cur;cur = cur->next;}return nullptr;//不相交}
};

方法2:A中的每个结点和B分别比较(B和A比较也可以),看二者的地址是否一致 - O(N*M)

class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {ListNode* curA = headA;ListNode* curB = headB;while(curA) //确定一个A节点{curB = headB;while(curB)//遍历整条B链表{if(curA == curB){return curA;}curB = curB ->next;}curA = curA->next;}return nullptr;}
};

方法3:

1.先统计两条链表的长度,假设二者长度差距为gap

2.长链表先往后走gap步,然后长短链表一起往后走,如果相遇,那么就是相交节点

class Solution {public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {if(!headA || !headB) return nullptr;//1.统计两条链表的长度int lenA = 0;int lenB = 0;ListNode* cur = headA;while(cur)  lenA++,cur = cur->next;cur = headB;

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

IDEA常用工具配置

IDEA常用工具&配置 如果发现插件市场用不了&#xff0c;可以设置Http Proxy&#xff0c;在该界面上点击”Check connection“并输入的地址&#xff1a;https://plugins.jetbrains.com/ 。 一、常用插件 1、MybatisX Mybaits Plus插件&#xff0c;支持java与xml互转 2、F…

vue上传图片并修改png图片颜色

场景 当涉及到在 Vue 中上传图片并修改 PNG 图片的颜色时&#xff0c;这个任务涵盖了文件上传、图像处理、Canvas 操作等多个方面 在现代 Web 开发中&#xff0c;图片的处理是常见的需求之一。本文将带您深入探讨如何使用 Vue.js 来实现图片上传&#xff0c;并在客户端使用 Can…

LD_RPELOAD环境变量

目录 LD_RPELOAD环境变量 LD_RPELOAD 定义 程序的连接方式 Linux规定动态链接库的文件名规则如下 动态链接库的搜索路径搜索的先后顺序 LD_RPELOAD的劫持 demo 1.定义一个hook.c文件 2.将所写的hook.c 文件编译为动态链接库hook.so 3.劫持检测&#xff0c;查看LD_PREL…

WebMagic - 创意前端项目集合(点击链接可在电脑上查看效果)

WebMagic - 创意前端项目集合 欢迎来到 WebMagic 仓库&#xff01;这里汇集了一系列令人惊叹的前端项目&#xff0c;涵盖了HTML5、CSS3和JS等多项技术。无论你是前端开发者、设计师&#xff0c;还是对创意互动内容感兴趣的人&#xff0c;这个仓库都将为你带来无尽的惊喜。 每…

第07天 Static关键字作用及用法

✅作者简介&#xff1a;大家好&#xff0c;我是Leo&#xff0c;热爱Java后端开发者&#xff0c;一个想要与大家共同进步的男人&#x1f609;&#x1f609; &#x1f34e;个人主页&#xff1a;Leo的博客 &#x1f49e;当前专栏&#xff1a;每天一个知识点 ✨特色专栏&#xff1a…

Kubernetes网络组件详解

目录 1、Kubernetes网络组件 1.1、Flannel网络组件 1.2、Calico 网络插件 2、环境准备 2.2、部署docker环境 3、部署kubernetes集群 3.1、组件介绍 3.2、配置阿里云yum源 3.3、安装kubelet kubeadm kubectl 3.4、配置init-config.yaml 3.5、安装master节点 3.6、安…

MySQL高可用MHA

目录 前言 一、概述 二、配置免密、组从复制 三、MHA配置 四、测试 总结 前言 MySQL高可用管理工具&#xff08;MHA&#xff0c;Master High Availability&#xff09;是一个用于自动管理MySQL主从复制的工具&#xff0c;它可以提供高可用性和自动故障转移。MHA由原版的MHA工具…

web前端tips:js继承——组合继承

上篇文章给大家分享了 js继承中的借用构造函数继承 web前端tips&#xff1a;js继承——借用构造函数继承 在借用构造函数继承中&#xff0c;我提到了它的缺点 无法继承父类原型链上的方法和属性&#xff0c;只能继承父类构造函数中的属性和方法 父类的方法无法复用&#xff0…

【算法】双指针划分思想妙解移动零

Problem: 283. 移动零 文章目录 思路算法图解分析复杂度Code 思路 首先我们来讲一下本题的思路 本题主要可以归到【数组划分/数组分块】这一类的题型。我们将一个数组中的所有元素划分为两段区间&#xff0c;左侧是非零元素&#xff0c;右侧是零元素 那解决这一类的题我们首先想…

蓝帽杯 取证2022

网站取证 网站取证_1 下载附件 并解压 得到了一个文件以及一个压缩包 解压压缩包 用火绒查病毒 发现后门 打开文件路径之后 发现了一句话木马 解出flag 网站取证_2 让找数据库链接的明文密码 打开www文件找找 查看数据库配置文件/application/database.php&#xff08;CodeI…

【网络】网络层——IP协议

&#x1f431;作者&#xff1a;一只大喵咪1201 &#x1f431;专栏&#xff1a;《网络》 &#x1f525;格言&#xff1a;你只管努力&#xff0c;剩下的交给时间&#xff01; 网络层中&#xff0c;IP协议首部和有效载荷组成的完整数据称为数据报。 IP协议 &#x1f349;TCP和IP的…

网络安全 Day31-运维安全项目-容器架构下

容器架构下 6. Dockerfile6.1 Docker自动化DIY镜像之Dockerfile1) 环境准备2) 书写Dockerfile内容3&#xff09; 运行Dockerfile生成镜像4) 运行容器5) 小结 6.2 案例14&#xff1a;Dockerfile-RUN指令1) 书写Dockerfile2) 构建镜像3) 启动容器4) 测试结果 6.3 Dockerfile指令 …

解决生成式AI落地之困,亚马逊云科技提供完整解决方案

生成式AI技术无疑是当前最大的时代想象力之一。 资本、创业者、普通人都在涌入生成式AI里去一探究竟&#xff1a;“百模大战”连夜打响&#xff0c;融资规模连创新高&#xff0c;各种消费类产品概念不断涌现……根据Bloomberg Intelligence 的报告&#xff0c;2022年生成式AI 市…

LeetCode--HOT100题(31)

目录 题目描述&#xff1a;25. K 个一组翻转链表&#xff08;困难&#xff09;题目接口解题思路代码 PS: 题目描述&#xff1a;25. K 个一组翻转链表&#xff08;困难&#xff09; 给你链表的头节点 head &#xff0c;每 k 个节点一组进行翻转&#xff0c;请你返回修改后的链表…

如何避免爬虫IP被屏蔽

各位爬友们好&#xff0c;作为一名专业的爬虫代理提供者&#xff0c;我要和大家分享一些避免爬虫IP被屏蔽的实用技巧。你知道吗&#xff0c;当我们爬取数据的时候&#xff0c;很容易被目标网站识别出来并封禁我们的IP地址&#xff0c;导致无法继续爬取数据。这个问题困扰了很多…

邀请函|澎峰科技邀您参加CCF HPC China2023

一年一度的全球超算盛会&#xff01; 以“算力互联智领未来”为主题的第十九届全国高性能计算学术年会&#xff08;CCF HPC China 2023&#xff09;将于8月24-26日&#xff08;展览23-25日&#xff09;在青岛红岛国际会议展览中心举办。 九大院士领衔 打造顶级超算盛会 力邀…

【前端|Javascript第5篇】全网最详细的JS的内置对象文章!

前言 在当今数字时代&#xff0c;前端技术正日益成为塑造用户体验的关键。我们在开发中需要用到很多js的内置对象的一些属性来帮助我们更快速的进行开发。或许你是刚踏入前端领域的小白&#xff0c;或者是希望深入了解内置对象的开发者&#xff0c;不论你的经验如何&#xff0c…

Linux:shell脚本:基础使用(4)《正则表达式-grep工具》

正则表达式定义&#xff1a; 使用单个字符串来描述&#xff0c;匹配一系列符合某个句法规则的字符串 正则表达式的组成&#xff1a; 普通字符串: 大小写字母&#xff0c;数字&#xff0c;标点符号及一些其他符号 元字符&#xff1a;在正则表达式中具有特殊意义的专用字符 正则表…

OpenCV-Python中的图像处理-图像特征

OpenCV-Python中的图像处理-图像特征 图像特征Harris角点检测亚像素级精度的角点检测Shi-Tomasi角点检测SIFT(Scale-Invariant Feature Transfrom)SURF(Speeded-Up Robust Features)FAST算法BRIEF(Binary Robust Independent Elementary Features)算法ORB (Oriented FAST and R…

中睿天下受邀参加第六届电力信息通信新技术大会并发表主题演讲

2023年8月9-11日&#xff0c;中国电力企业联合会科技开发服务中心以“加快数字化转型助力新型电力系统建设”为主题&#xff0c;在杭州举办2023年&#xff08;第六届&#xff09;电力信息通信新技术大会暨数字化发展论坛。 大会旨在加快推进“双碳”目标下的新型能源体系和新型…