当前位置： 首页 > news >正文

leetCode- - - 链表

news 来源：原创 2024/9/20 2:57:47

目录

1.反转链表（leetcode206）

2. 链表内指定区间反转（leetcode92）

3.链表中的节点每k个一组翻转（leetcode25）

4.合并两个排序的链表（leetcode21）

5.链表的中间节点（leetcode876）

6.重排链表（leetcode143）

7.旋转链表（leetcode61）

8.删除排序链表中的重复元素（leetcode83）

9.删除排序链表中的重复元素（LeetCode 82）（迭代版）

10.环形链表 II （ LeetCode 142 ）

11.回文链表（ LeetCode 234 ）

12.相交链表（ LeetCode 160 ）

13.奇偶链表（ LeetCode 328 ）

14.移除链表元素（ LeetCode 203 ）

15.链表题目做题总结

1.反转链表（leetcode206）

import java.util.*;/** public class ListNode {*   int val;*   ListNode next = null;*   public ListNode(int val) {*     this.val = val;*   }* }*/public class Solution {/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param head ListNode类 * @return ListNode类*/public ListNode ReverseList (ListNode head) {// write code hereListNode prev=null;ListNode cur=head;if(head==null){return null;}if(head.next==null){return head;}while(cur!=null){ListNode temp=cur.next;cur.next=prev;prev=cur;cur=temp;}return prev;}
}

2. 链表内指定区间反转（leetcode92）

import java.util.*;/** public class ListNode {*   int val;*   ListNode next = null;*   public ListNode(int val) {*     this.val = val;*   }* }*/public class Solution {/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param head ListNode类 * @param m int整型 * @param n int整型 * @return ListNode类*/public ListNode reverseBetween (ListNode head, int m, int n) {// write code hereListNode dummy=new ListNode(0);dummy.next=head;ListNode prev=dummy;for(int i=0;i<m-1;i++){prev=prev.next;}ListNode cur=prev.next;for(int i=0;i<n-m;i++){ListNode temp=cur.next;cur.next=temp.next;temp.next=prev.next;prev.next=temp;}return dummy.next;}
}

3.链表中的节点每k个一组翻转（leetcode25）

public class Solution {/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可*** @param head ListNode类* @param k int整型* @return ListNode类*/public ListNode reverseKeyGroup (ListNode head, int k) {// write code hereListNode tail=head;//1.递归结束的点for (int i = 0; i < k; i++) {if(tail==null){return head;}tail=tail.next;}//2.完成每k个元素内的翻转ListNode prev=null;ListNode cur=head;while (cur!=tail){ListNode temp=cur.next;cur.next=prev;prev=cur;cur=temp;}head.next=reverseKeyGroup(tail,k);return prev;}
}

4.合并两个排序的链表（leetcode21）

import java.util.*;/** public class ListNode {*   int val;*   ListNode next = null;*   public ListNode(int val) {*     this.val = val;*   }* }*/public class Solution {/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param pHead1 ListNode类 * @param pHead2 ListNode类 * @return ListNode类*/public ListNode Merge (ListNode pHead1, ListNode pHead2) {// write code hereListNode dummy =new ListNode(-1);ListNode prev=dummy;while(pHead1!=null && pHead2!=null){if(pHead1.val<pHead2.val){prev.next=pHead1;pHead1=pHead1.next;prev=prev.next;}else{prev.next=pHead2;pHead2=pHead2.next;prev=prev.next;}}if(pHead1!=null){prev.next=pHead1;}if(pHead2!=null){prev.next=pHead2;}return dummy.next;}
}

5.链表的中间节点（leetcode876）

解题：快慢指针

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

6.重排链表（leetcode143）

给定一个单链表 L 的头节点 head ，单链表 L 表示为：

L0 → L1 → … → Ln - 1 → Ln

请将其重新排列后变为：

L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …

不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public void reorderList(ListNode head) {//1.快慢指针找到中间节点，分成左右两个链表ListNode leftHead=head;ListNode mid=midNode(head);ListNode rightHead=mid.next;//断开左右两个链表mid.next=null;//2.反转右边的链表rightHead=reverse(rightHead);//3.交错合并左右链表while(leftHead!=null && rightHead!=null){ListNode leftHeadNext=leftHead.next;ListNode rightHeadNext=rightHead.next;leftHead.next=rightHead;leftHead=leftHeadNext;rightHead.next=leftHead;rightHead=rightHeadNext;}}public ListNode midNode(ListNode head){ListNode slow=head;ListNode fast=head;while(fast!=null && fast.next!=null){fast=fast.next.next;slow=slow.next;}return slow;}public ListNode reverse(ListNode head){ListNode prev=null;ListNode cur=head;if(head==null){return null;}if(head.next==null){return head;}while(cur!=null){ListNode temp=cur.next;cur.next=prev;prev=cur;cur=temp;}return prev;}
}

7.旋转链表（leetcode61）

给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode rotateRight(ListNode head, int k) {if(head==null || k==0){return head;}//计算出链表的长度，当k非常大时，走k步等于走k%len步ListNode cur=head;int len=0;while(cur!=null){len+=1;cur=cur.next;}k=k%len;//former指针先走k步ListNode former=head;ListNode later=head;for(int i=0;i<k;i++){former=former.next;}while(former.next!=null){former=former.next;later=later.next;}former.next=head;ListNode newHead=later.next;later.next=null;return newHead;}
}

8.删除排序链表中的重复元素（leetcode83）

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

class Solution {public ListNode deleteDuplicates(ListNode head) {ListNode cur=head;if(head==null || head.next==null){return head;}while(cur!=null && cur.next!=null){if(cur.val==cur.next.val){cur.next=cur.next.next;}else{cur=cur.next;}}return head;}

9.删除排序链表中的重复元素（LeetCode 82）（迭代版）

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

也可以使用递归的方式，个人认为迭代的方式更容易理解。

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode deleteDuplicates(ListNode head) {ListNode dummy=new ListNode(-1);dummy.next=head;ListNode cur=dummy;while(cur.next!=null && cur.next.next!=null){if(cur.next.val==cur.next.next.val){int value=cur.next.val;while(cur.next!=null && cur.next.val==value){cur.next=cur.next.next;}}else{cur=cur.next;}}return dummy.next;}
}

10.环形链表 II （ LeetCode 142 ）

给定一个链表的头节点  head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改 链表。

/*** Definition for singly-linked list.* class ListNode {*     int val;*     ListNode next;*     ListNode(int x) {*         val = x;*         next = null;*     }* }*/
public class Solution {public ListNode detectCycle(ListNode head) {ListNode fast=head;ListNode slow=head;while(fast!=null && fast.next!=null){fast=fast.next.next;slow=slow.next;if(fast==slow){ListNode b=fast;ListNode a=head;while(a!=b){a=a.next;b=b.next;}return a;}}return null;}
}

11.回文链表（ LeetCode 234 ）

给你一个单链表的头节点 head ，请你判断该链表是否为

回文链表

。如果是，返回 true ；否则，返回 false 。

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public boolean isPalindrome(ListNode head) {if(head.next==null){return true;}if(head.next.next==null){if(head.val==head.next.val){return true;}else{return false;}}//1.找到中间节点ListNode fast=head;ListNode slow=head;while(fast.next!=null && fast.next.next!=null){fast=fast.next.next;slow=slow.next;}//2.分割为两个链表ListNode leftHead=head;ListNode rightHead=slow.next;//3.反转右边链表rightHead= reverse(rightHead);//4.比较左右链表while (rightHead!=null){if(leftHead.val==rightHead.val){leftHead=leftHead.next;rightHead=rightHead.next;}else{return false;}}return true;}public ListNode reverse(ListNode head){ListNode pre=null;ListNode cur=head;while(cur!=null){ListNode temp=cur.next;cur.next=pre;pre=cur;cur=temp;}return pre;}
}

12.相交链表（ LeetCode 160 ）

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

图示两个链表在节点 c1 开始相交：

题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode(int x) {*         val = x;*         next = null;*     }* }*/
public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {ListNode pa=headA;ListNode pb=headB;if(headA==null || headB==null){return null;}while(pa!=pb){if(pa==null){pa=headB;}else{pa=pa.next;}if(pb==null){pb=headA;}else{pb=pb.next;}}return pa;}
}

13.奇偶链表（ LeetCode 328 ）

给定单链表的头节点 head ，将所有索引为奇数的节点和索引为偶数的节点分别组合在一起，然后返回重新排序的列表。

第一个节点的索引被认为是 奇数 ， 第二个节点的索引为 偶数 ，以此类推。

请注意，偶数组和奇数组内部的相对顺序应该与输入时保持一致。

你必须在 O(1) 的额外空间复杂度和 O(n) 的时间复杂度下解决这个问题。

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode oddEvenList(ListNode head) {//链表为空或者只有一个节点，直接返回即可if(head==null || head.next==null){return head;}ListNode odd=head;ListNode even=odd.next;ListNode evenHead=even;while(even!=null && even.next!=null){odd.next=even.next;    odd=odd.next;even.next=odd.next;even=even.next;}odd.next=evenHead;return head;}
}

14.移除链表元素（ LeetCode 203 ）

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

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode removeElements(ListNode head, int val) {if(head==null){return null;}ListNode dummy=new ListNode(-1);dummy.next=head;ListNode pre=dummy;ListNode cur=head;while(cur!=null){if(cur.val==val){pre.next=cur.next;}else{pre=cur;}cur=cur.next;}return dummy.next;}
}

15.链表题目做题总结


1.画图理清思路。
2.考虑边界条件：链表问题通常有很多边界条件需要考虑，例如空链表、只有一个节点的链表、链表长度为偶数或奇数等等。
3.双指针技巧

   快慢指针：用于找链表中点、检测环等问题。
   双指针一前一后：用于逆转链表、找倒数第k个节点等问题。
   双指针同向移动：用于合并两个有序链表等问题。
4.递归的应用：
   有些链表问题可以通过递归来简化处理，例如逆转链表、检测回文链表等。
5.注意内存管理：
   如果涉及到链表节点的删除或插入，要确保不会造成内存泄漏或者指针丢失。特别是在删除节点时，要注意处理好被删除节点的前驱和后继节点的指针关系。
6.利用哨兵节点简化操作：
   在一些操作中，使用哨兵节点（dummy node）可以简化边界条件的处理，特别是在涉及头节点操作时特别有效。
 

相关文章：

  • 北京网站建设多少钱？
  • 辽宁网页制作哪家好_网站建设
  • 高端品牌网站建设_汉中网站制作
  • 工业设备数据采集方案的设计实施与应用-天拓四方
  • Redis--缓存击穿、缓存穿透、缓存雪崩
  • 21-原理图的可读性的优化处理
  • 【DataKit系列】数据迁移-实例搭建步骤（二）
  • 使用GCC编译Notepad++的插件
  • 【Python数据处理】MatplotlibNumpyPandas常用API整理
  • MySQL学习（19）：锁
  • CSS文本两端对齐
  • StringJoiner更优雅创建含分隔符的字符序列
  • k8s数据卷(volume)管理
  • 深度学习 - 数据存储形式对比(pkl/CSV/JSON等)
  • 设计模式的概念
  • qt-声明、宏
  • 【深度学习】【语音】TTS，Matcha-TTS，测试效果，训练中文，chinese
  • YOLOv8添加MobileViTv3模块（代码+free）
  • 【腾讯Bugly干货分享】从0到1打造直播 App
  • Computed property XXX was assigned to but it has no setter
  • ES6 学习笔记（一）let，const和解构赋值
  • ES6语法详解(一)
  • ESLint简单操作
  • Golang-长连接-状态推送
  • iOS高仿微信项目、阴影圆角渐变色效果、卡片动画、波浪动画、路由框架等源码...
  • MySQL主从复制读写分离及奇怪的问题
  • Python实现BT种子转化为磁力链接【实战】
  • Python学习之路16-使用API
  • Sass 快速入门教程
  • SpiderData 2019年2月23日 DApp数据排行榜
  • Vue2.x学习三：事件处理生命周期钩子
  • 不上全站https的网站你们就等着被恶心死吧
  • 工程优化暨babel升级小记
  • 关于使用markdown的方法（引自CSDN教程）
  • 将回调地狱按在地上摩擦的Promise
  • 入口文件开始，分析Vue源码实现
  • 深度解析利用ES6进行Promise封装总结
  • ［地铁译］使用SSD缓存应用数据——Moneta项目: 低成本优化的下一代EVCache ...
  • 好程序员web前端教程分享CSS不同元素margin的计算 ...
  • ​批处理文件中的errorlevel用法
  • # 数仓建模：如何构建主题宽表模型？
  • ## 1.3.Git命令
  • #{}和${}的区别是什么 -- java面试
  • #define MODIFY_REG(REG, CLEARMASK, SETMASK)
  • #gStore-weekly | gStore最新版本1.0之三角形计数函数的使用
  • #基础#使用Jupyter进行Notebook的转换 .ipynb文件导出为.md文件
  • #我与Java虚拟机的故事#连载06：收获颇多的经典之作
  • （1综述）从零开始的嵌入式图像图像处理(PI+QT+OpenCV)实战演练
  • （C语言）输入一个序列，判断是否为奇偶交叉数
  • （Java实习生）每日10道面试题打卡——JavaWeb篇
  • (js)循环条件满足时终止循环
  • （草履虫都可以看懂的）PyQt子窗口向主窗口传递参数，主窗口接收子窗口信号、参数。
  • （二）WCF的Binding模型
  • （附源码）springboot工单管理系统 毕业设计 964158
  • （十八）devops持续集成开发——使用docker安装部署jenkins流水线服务
  • （实测可用）（3）Git的使用——RT Thread Stdio添加的软件包，github与gitee冲突造成无法上传文件到gitee
  • （数据大屏）（Hadoop）基于SSM框架的学院校友管理系统的设计与实现+文档
  • （五）Python 垃圾回收机制