【数据结构练习题】单链表问题解决（虚拟头节点法，递归，快慢指针法）

news/2025/2/12 4:00:47/

目录

  • 1.删除单链表中的元素
    • 1.1 删除排序链表中的重复元素
    • 1.2 删除排序链表中的重复元素Ⅱ
    • 1.3 移除链表元素
  • 2.反转链表
    • 2.1 反转链表
    • 2.2 反转链表Ⅱ
  • 3.查找链表中结点
    • 3.1 链表的中间结点
    • 3.2 链表中倒数第k个节点
  • 4.回文链表
  • 5.相交链表
  • 6.合并链表

知识补充：

递归三要素：

  1. 大问题能拆成若干个小问题的解。
  2. 拆分后的子问题和原问题除了数据规模不同，思路完全相同。
  3. 存在问题的终止条件，不借助任何外部函数的特殊值，直接得出答案。

链表问题三大常用方法：

  1. 虚拟头节点法
  2. 递归
  3. 快慢指针法

1.删除单链表中的元素

1.1 删除排序链表中的重复元素

题目链接： 83.删除链表中的重复元素

题目内容：给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次返回已排序的链表 。

示例：
在这里插入图片描述
输入：head = [1,1,2,3,3]
输出：[1,2,3]

解法1：迭代

要找重复元素，这里使用两个引用：prev，cur

  1. base case：若链表为空或只有一个元素，肯定不会有重复元素，直接返回即可。
  2. 当链表长度大于1时，给定一个虚拟头结点，让prev指向虚拟头结点，cur指向后一个节点。判断这两个节点的值是否相同。
  3. 若不相同，则prev=prev.next。
  4. 若相同，prev.next=cur.next，使prev指向相同元素节点的下一个节点,cur=cur.next，再继续判断，重复以上过程。
  5. 最后返回dummyHead.next即可。

在这里插入图片描述

    public ListNode deleteDuplicates(ListNode head) {//base caseif(head==null || head.next==null){return head;}//此时链表一定两个节点//虚拟头节点ListNode dummyhead=new ListNode(-101);dummyhead.next=head;//prev指向的一定不是重复元素ListNode prev=dummyhead;//双指针比较元素是否重复ListNode cur=prev.next;while(cur!=null){if(prev.val==cur.val){prev.next=cur.next;}else{prev=prev.next;}cur=cur.next;}return dummyhead.next;}

解法2：递归

链表是天然的递归结构。

首先，明确deleteDuplicates()方法的作用是删除所有重复的元素，得到一个所有元素只出现一次的已排序的链表 。

那么，整个链表就可以分为 head+除head以外的所有节点
在这里插入图片描述
即head+deleteDuplicates(head.next)
此时deleteDuplicates(head.next)已经是一个没有重复元素的链表，那么只需要判断head和此链表的head的值是否相同。

步骤：

  1. 边界条件，若链表为空或只有一个元素，肯定不会有重复元素，直接返回即可。
  2. 要删除重复元素，先把以head.next为头结点的子链表中的所有重复元素删除完。
  3. 最后比较head和head.next的值。
    public ListNode deleteDuplicates(ListNode head) {//base caseif(head==null || head.next==null){return head;}head.next=deleteDuplicates(head.next);return head.val==head.next.val ? head.next:head;}

1.2 删除排序链表中的重复元素Ⅱ

题目链接： 82.删除排序链表中的重复元素Ⅱ

题目内容： 给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。

示例：
在这里插入图片描述
输入：head = [1,2,3,3,4,4,5]
输出：[1,2,5]

本题和上一题不同的地方在于，只留下不同的元素，重复元素一个不留。

解法1：迭代

这里使用三指针法：prev,cur,sec

  • prev一定指向不同元素
  • sec一定指定cur的下一个

在这里插入图片描述

步骤：

  1. 边界条件，若链表为空或只有一个元素，肯定不会有重复元素，直接返回即可。
  2. 当sec==null时，循环结束，没有可比较的对象了。
  3. 当cur.val != sec.val，prev=prev.next，prev向后移动。
  4. 当cur.val==sec.val时，循环判断，sec一直向后移动，直到cur.val != sec.val，此时prev.next指向sec。
  5. cur移动到sec的位置。在新一轮循环中，让sec=cur.next。继续判断。
public ListNode deleteDuplicates(ListNode head) {//base caseif(head==null || head.next==null){return head;}//虚拟头结点ListNode dummyHead=new ListNode(-101);dummyHead.next=head;ListNode prev=dummyHead;ListNode cur=prev.next;while(cur!=null){ListNode sec=cur.next;if(sec==null){break;}if(cur.val!=sec.val){prev=prev.next;}else{while( sec!=null && cur.val==sec.val){sec=sec.next;}//此时,sec和cur一定不相等prev.next=sec;}cur=sec;}return dummyHead.next;}

解法2：递归

链表可以看作head以head.next为头结点的子链表的组合。
在这里插入图片描述

思路：

  1. 边界条件，若链表为空或只有一个元素，肯定不会有重复元素，直接返回即可。
  2. 若head.val !=head.next.val，head.next直接指向以head.next为头结点的链表。
  3. 若head.val ==head.next.val，此时头结点就是重复的节点，先处理头结点的情况，给定一个引用newHead等于head.next。判断head.val==newHead.val，若相等，让newHead不停向后移动，直到不相等。此时newHead一定不是重复元素，返回deleteDuplicates(newHead)。
    public ListNode deleteDuplicates(ListNode head) {//base caseif(head==null || head.next==null){return head;}if(head.val !=head.next.val){head.next=deleteDuplicates(head.next);return head;}else{//头结点就是重复的节点，先处理完头结点的情况ListNode newHead=head.next;while(newHead!=null && head.val==newHead.val){newHead=newHead.next;}//此时newHead一定不是重复元素return(deleteDuplicates(newHead));}}

1.3 移除链表元素

题目链接： 203.移除链表元素

题目内容： 给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

示例：
在这里插入图片描述
输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]

解法1：迭代

思路：

  1. 边界条件，如何head为空，直接返回null。
  2. 给定一个虚拟头结点，连接head。给定一个引用prev指向虚拟头结点。（注意：prev一定指向值不为val的节点）
  3. 遍历链表。若prev.next.val==val，prev直接指向prev.next的下一个节点。
  4. 若不相等，prev直接向后移动。
		public ListNode removeElements(ListNode head, int val) {//1.base caseif(head==null){return null;}//虚拟头节点ListNode dummyHead=new ListNode();dummyHead.next=head;//prev一定指向值不为val的节点ListNode prev=dummyHead;while(prev.next!=null){if(prev.next.val==val){prev.next=prev.next.next;}else{prev=prev.next;}}return dummyHead.next;}

解法2：递归

链表可以看作head以head.next为头结点的子链表的组合。
在这里插入图片描述

思路：

  1. 边界条件，如何head为空，直接返回null。
  2. removeElements(head.next,val)一定是值不为val的链表。head.next直接指向removeElements(head.next,val)。
  3. 此时只需判断头节点的值是否为val。若是，返回head.next，否则返回head。
    public ListNode removeElements(ListNode head, int val) {//base caseif(head==null){return null;}head.next=removeElements(head.next,val);return head.val==val ? head.next:head;}

2.反转链表

2.1 反转链表

题目链接：206.反转链表

题目内容： 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例：
在这里插入图片描述
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

解法1：头插法

思路：若题目没有空间限制，则可以遍历原链表，不断产生新节点，在头插到新链表中，最后返回新链表。

   public ListNode reverseList(ListNode head) {//base case if(head==null || head.next==null){return head;}//虚拟头结点ListNode dummyHead=new ListNode(-1);//不断遍历原链表，产生新节点，头插到新链表while(head!=null){ListNode cur=new ListNode(head.val);cur.next=dummyHead.next;dummyHead.next=cur;head=head.next;}return dummyHead.next;}

解法2：原地反转

思路：

  1. 原先prev是指向cur的，反过来，让cur指向prev就实现了反转。
  2. 但是cur.next指向prev之后，剩下的链表就断开了找不到了，所以需要先用一个next记住原链表cur的下一个节点。
    当cur为null时，prev刚好在最后一个节点，直接返回prev即可。

在这里插入图片描述

    public ListNode reverseList(ListNode head) {//base caseif(head==null || head.next==null){return null;}ListNode prev=null;ListNode cur=head;while(cur!=null){ListNode next=cur.next;cur.next=prev;prev=cur;cur=next;}return prev;}

解法3：递归

思路：

  1. reverseList(ListNode head)的作用是得到一个反转后的链表。

  2. 则可以把链表分为头节点和以head.next为头节点的反转后的链表。

  3. 此时只需要将head连接到子链表的尾端即可。

在这里插入图片描述

    public ListNode reverseList(ListNode head) {if(head==null || head.next==null){return head;}ListNode next=head.next;ListNode newHead=reverseList(head.next);//拼接当前头节点和转后的子链表head.next=null;next.next=head;return newHead;}

2.2 反转链表Ⅱ

题目链接：92.反转链表Ⅱ

解法：

思路：

  1. 给定两个引用，记住left的前一个节点和right的后一个节点。
  2. 先将待反转的区域反转
  3. 把 pre 的 next 指针指向反转以后的链表头节点，把反转以后的链表的尾节点的 next 指针指向 succ。

在这里插入图片描述

    public ListNode reverseBetween(ListNode head, int left, int right) {//base caseif(head==null || head.next==null){return head;}ListNode dummyHead=new ListNode(-1);dummyHead.next=head;ListNode prev=dummyHead;//从temp开始走，来到left的前一个节点for(int i=0;i<left-1;i++){prev=prev.next;}//从prev开始走，一直到right节点ListNode rightNode=prev;for(int i=0;i<right-left+1;i++){rightNode=rightNode.next;}//截取要反转的链表ListNode next=rightNode.next;ListNode leftNode=prev.next;//切断连接prev.next=null;rightNode.next=null;//反转链表子区间reverseList(leftNode);//接回原链表prev.next=rightNode;leftNode.next=next;return dummyHead.next;}public ListNode reverseList(ListNode head) {ListNode prev=null;ListNode cur=head;while(cur!=null){ListNode next=cur.next;cur.next=prev;prev=cur;cur=next;}return prev;}

3.查找链表中结点

3.1 链表的中间结点

题目链接：876.链表的中间结点

题目内容： 给你单链表的头结点 head ，请你找出并返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。

示例：
在这里插入图片描述
输入：head = [1,2,3,4,5]
输出：[3,4,5]
解释：链表只有一个中间结点，值为 3 。

解法1：按长度查找

步骤：

  1. 遍历原链表，得到链表的长度
  2. 若长度为奇数，直接走 长度/2 的步数。
  3. 若长度为偶数，也是直接走 长度/2 的步数。
    public ListNode middleNode(ListNode head) {int count=0;ListNode temp=head;while(temp!=null){temp=temp.next;count++;}int n=count/2;while(n>0){head=head.next;n--;}return head;}

解法2：快慢指针法

思路：

  1. 两个指针,low 和 fast
  2. low每走一步，fast就走两步
  3. 当fast走到终点，low就停在我们想要的位置

在这里插入图片描述

    public ListNode middleNode(ListNode head) {ListNode low=head;ListNode fast=head;while(fast!=null && fast.next!=null){low=low.next;fast=fast.next.next;}return low;}

3.2 链表中倒数第k个节点

题目链接：剑指Offer 22.链表中倒数第k个结点

题目内容： 输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。

示例：

给定一个链表: 1->2->3->4->5, 和 k = 2.

返回链表 4->5.

解法1：按长度查找

思路：

  1. 遍历链表，得到链表的长度n。
  2. 倒数第k个结点就是正数第n-k个结点。
    public ListNode getKthFromEnd(ListNode head, int k) {if(head==null || k<=0){return null;}ListNode temp=head;int n=0;while(temp!=null){temp=temp.next;n++;}int count=n-k;while(count>0){head=head.next;count--;}return head;}

解法2：快慢指针法

思路：

  1. 给定两个引用sec，fir
  2. fir先向前走k步。
  3. sec 和 fir 同时向前走，当fir为null时，sec刚好指向倒数dik个结点。

在这里插入图片描述

    public ListNode getKthFromEnd(ListNode head, int k) {if(head==null || k<=0){return null;}ListNode fir=head;ListNode sec=head;for(int i=0;i<k;i++){//判断k>链表长度的情况if(fir==null){return null;}fir=fir.next;}while(fir!=null){fir=fir.next;sec=sec.next;}return sec;}

4.回文链表

题目链接：234.回文链表

题目内容： 给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

示例：
在这里插入图片描述
输入：head = [1,2,2,1]
输出：true

解法

思路：

  1. 判断回文链表其实就是判断对称链表。
  2. 将链表一份为二，l1为头节点到中间结点的链表，l2为中间结点到尾节点的链表。
  3. 将l2反转，与l1的值进行对比。遍历，直到其中一条链表走到null，若有不一样的值，则不为回文链表。反之，则是回文链表。

在这里插入图片描述

   public boolean isPalindrome(ListNode head) {if(head==null || head.next==null){return true;}ListNode middleNode=middleNode(head);//反转中间结点之后的链表ListNode l2=reverseList(middleNode);//找反例while(head!=null && l2!=null){if(head.val != l2.val){return false;}head=head.next;l2=l2.next;}return true;}//查找中间节点public ListNode middleNode(ListNode head) {int count=0;ListNode temp=head;while(temp!=null){temp=temp.next;count++;}int n=count/2;while(n>0){head=head.next;n--;}return head;}//反转链表public ListNode reverseList(ListNode head) {if(head==null || head.next==null){return head;}ListNode next=head.next;ListNode newHead=reverseList(head.next);//拼接当前头节点和转后的子链表head.next=null;next.next=head;return newHead;}

5.相交链表

题目链接：160.相交链表

题目内容： 给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

示例：
在这里插入图片描述
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at ‘8’
解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,6,1,8,4,5]。
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
— 请注意相交节点的值不为 1，因为在链表 A 和链表 B 之中值为 1 的节点 (A 中第二个节点和 B 中第三个节点) 是不同的节点。换句话说，它们在内存中指向两个不同的位置，而链表 A 和链表 B 中值为 8 的节点 (A 中第三个节点，B 中第四个节点) 在内存中指向相同的位置。

解法：

如图所示：

  • listA的长度=x+z
  • listB的长度=y+z

但若让A和B都走一遍对方的路程：即 x+z+y=y+z+x。此时它们的路程一定相等，走完之后一定会相交。

在这里插入图片描述
过程图举例：
在这里插入图片描述

步骤：

  1. 引入两个引用listA，listB。
  2. listA走到终点后倒过来走listB。
  3. listB走到终点后倒过来走listA。
  4. 若不存在交点，则listA和listB最后都指向null。
  5. 若存在交点，则两个链表走完全程后一定指向交点。
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {//引入两个引用ListNode listA=headA;ListNode listB=headB;while(listA!=listB){listA = listA==null ? headB:listA.next;listB = listB==null ? headA:listB.next;}return listA;}

6.合并链表

题目链接：21.合并两个有序链表

题目内容： 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例：
在这里插入图片描述
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

解法1：虚拟头节点法

思路：

  1. 给定一个虚拟头结点dummyHead；
  2. 遍历两个链表。比较结点值的大小，将较小值拼接在新链表后面。

图解：

在这里插入图片描述

    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {if(list1==null){return list2;}if(list2==null){return list1;}ListNode dummyHead=new ListNode(-1);ListNode tail=dummyHead;//取较小值拼接在链表的尾部while(list1!=null && list2!=null){if(list1.val<list2.val){tail.next=list1;tail=list1;list1=list1.next;}else{tail.next=list2;tail=list2;list2=list2.next;}}//此时，至少一个链表为Nullif(list1==null){tail.next=list2;}if(list2==null){tail.next=list1;}return dummyHead.next;}

解法2：递归

思路：

  1. 已知 mergeTwoLists(ListNode list1, ListNode list2)方法的作用是将两个升序链表合并为一个新的 升序 链表并返回。
  2. 如果list1.val<list2.val，此题可以看作list1+ mergeTwoLists(ListNode list1.next, ListNode list2)
  3. 如果list2.val<list1.val，此题可以看作list2+ mergeTwoLists(ListNode list1, ListNode list2.next)
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {if(list1==null){return list2;}if(list2==null){return list1;}if(list1.val<=list2.val){list1.next=mergeTwoLists(list1.next,list2);return list1;}else{list2.next=mergeTwoLists(list1,list2.next);return list2;}}

http://www.ppmy.cn/news/1004190.html

相关文章

AR远程专家指导在汽车改装上的应用有哪些？

AR远程专家指导在汽车改装上的应用有哪些？

随着科技的不断发展&#xff0c;AR增强现实技术逐渐走进了我们的生活。加上商贸国际化&#xff0c;远程协同纵深到制造生产的更多环节&#xff0c;研发协同、工艺优化等场景复杂、跨层级、需要频繁沟通确认的流程正通过AR应用实现全面远程化的过渡&#xff0c;在汽车行业&#…
阅读更多...
【设计模式——学习笔记】23种设计模式——迭代器模式Iterator（原理讲解+应用场景介绍+案例介绍+Java代码实现）

【设计模式——学习笔记】23种设计模式——迭代器模式Iterator（原理讲解+应用场景介绍+案例介绍+Java代码实现）

文章目录 案例引入介绍基础介绍应用场景登场角色 案例实现案例一实现 案例二实现 迭代器模式在JDK源码中的应用总结文章说明 案例引入 编写程序展示一个学校院系结构: 需求是这样&#xff0c;要在一个页面中展示出学校的院系组成&#xff0c;一个学校有多个学院&#xff0c;一…
阅读更多...
排序进行曲-v4.0

排序进行曲-v4.0

文章目录 小程一言快速排序步骤详细解释具体步骤 举例总结 复杂度分析时间复杂度分析&#xff1a;空间复杂度分析&#xff1a;注意 应用场景总结 实际举例结果总结 代码实现结果解释 小程一言 这篇文章是在排序进行曲3.0之后的续讲&#xff0c; 这篇文章主要是对快速排序进行细…
阅读更多...
线上Zookeeper问题解决记录

线上Zookeeper问题解决记录

zookeeper问题: 日志目录: /home/cmccdata/app/zookeeper/logs dataDir/home/cmccdata/app/zookeeper/data/zoodata dataLogDir/home/cmccdata/app/zookeeper/data/zoolog 问题0: 2023-08-03 17:15:43,139 [myid:1] - WARN [NIOServerCxn.Factory:0.0.0.0/0.0.0.0:2181:…
阅读更多...
分布式异步任务处理组件（五）

分布式异步任务处理组件（五）

节点上线和下线的逻辑-- 节点下线分为两种--心跳失败主动或被动和主节点断开连接&#xff0c;但是节点本身没有发生重启&#xff1b;第二种就是节点宕机重启--其实这两中情况下处理逻辑都是一样的&#xff0c;只是节点本身如果还能消费到kafka的时候可以继续执行任务但是不能从…
阅读更多...
pycharm——漏斗图

pycharm——漏斗图

import pyecharts.options as opts from pyecharts.charts import Funnel""" Gallery 使用 pyecharts 1.1.0 参考地址: https://echarts.apache.org/examples/editor.html?cfunnel目前无法实现的功能:1、暂时无法对漏斗图的长宽等范围操作进行修改 ""…
阅读更多...
LoVT：医学图像与报告的局部表征联合学习

LoVT：医学图像与报告的局部表征联合学习

论文&#xff1a;https://arxiv.org/abs/2112.02889 Github&#xff1a;GitHub - philip-mueller/lovt: Localized representation learning from Vision and Text (LoVT) 摘要 摘要对比学习已被证明对未标记数据的预训练图像模型是有效的&#xff0c;在医学图像分类等任务中…
阅读更多...
jQuery编程（jQuery概述、基本使用、常用API(jQuery选择器、样式操作、效果、属性操作、内容文本值、元素操作、尺寸位置操作)）

jQuery编程（jQuery概述、基本使用、常用API(jQuery选择器、样式操作、效果、属性操作、内容文本值、元素操作、尺寸位置操作)）

1.概述 1.1 JavaScript库 JavaScript库&#xff1a;即一个js文件&#xff0c;是一个封装好的特定的集合&#xff08;方法和函数&#xff09;。从封装一大堆函数的角度理解库&#xff0c;就是在这个库中&#xff0c;封装了很多预定好的函数在里面&#xff0c;比如动画animate、…
阅读更多...
最新文章

Copyright @ 2022~2023