LeetCode算法之--链表系列_链表类leetcode
赞
踩
点赞收藏，以防遗忘
本文【程序大视界】已收录，关注免费领取互联网大厂学习资料，添加博主好友进群学习交流，欢迎留言和评论，一起交流共同进步。
目录
【一】前言
2022经济寒冬之下，在年末之际来得更为惨烈，企鹅、宇宙等大厂相继爆出裁员消息后，某米，某站等也大批量裁员。不由得感叹，互联网的时代如今真的一去不复返了！作为互联网搬运工，码农们是最大的受害者，年底了短时间无法快速找到合适的下家，一个原因是迫于经济形势压力很多大厂都在收缩HC，另一个原因是大量的应届和被裁工程师都加入到找工作大军里面。这个形势下要找到下一份心仪的合适的令人向往的大厂offer，竞争就变得异常激烈了！唯有提升自己才是王道，面试中考算法已经变得非常普遍了，平时工作没有时间好好地练习算法，短时间内快速掌握算法技巧应对面试是重中之重。常用的算法有：动态规划、贪心算法、回溯算法、深度优先、广度优先、递归、双指针、快慢指针、迭代、哈希、二分等。
链表系列是算法题里面常见题型，通常涉及哈希、迭代、指针、递归的算法，下面介绍几个LeetCode上关于链表的题目。
【二】合并链表
LeetCode 21. 合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 1：
输入：l1 = [1,2,4], l2 = [1,3,4] 输出：[1,1,2,3,4,4]
示例 2：
输入：l1 = [], l2 = [] 输出：[]
示例 3：
输入：l1 = [], l2 = [0] 输出：[0]
提示：
- 两个链表的节点数目范围是
[0, 50] -100 <= Node.val <= 100l1和l2均按 非递减顺序 排列
【解法一】普通迭代：新建一个新的链表，用以存储合并链表的元素值，遍历并比较l1和l2两个链表元素值大小，小的那个放到新的合并链表末尾，直到遍历完两个链表后，最后判断两个链表是否都为空了，如果不为空则把剩余的元素添加到合并链表的末尾。
- class Solution {
- public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
- if(list1 == null){
- return list2;
- }
- if(list2 == null){
- return list1;
- }
- ListNode headerNode = new ListNode(-1);
- ListNode merge = headerNode;
- if(list1 != null && list2 != null){
- if(list1.val <= list2.val){
- merge.next = list1;
- list1 = list1.next;
- }else{
- merge.next = list2;
- list2 = list2.next;
- }
- merge = merge.next;
- }
- //最后要判断一下list1和list2是否都为空，不为空则把剩余节点添加到merge末尾
- merge.next = list1==null?list2:list1;
-
- return merge.next ;
- }
- }
【解法二】递归解法：递归的终止条件，如果l1或l2两个中的某个链表为空，则直接返回另外一个链表，递归条件，当l1的元素节点的值比l2小的时候，继续递归该方法，l1的next为左参数值，否则当l2的元素节点值比l1小的时候，继续递归该方法l2的next节点为方法的左参数值，继续递归该函数。
- class Solution {
- public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
- if(list1 == null){
- return list2;
- }
- if(list2 == null){
- return list1;
- }
- if((list1.val <= list2.val ){
- ListNode pNode = mergeTwoLists(list1.next,list2);
- return pNode;
- }else{
- ListNode pNode = mergeTwoLists(list2.next,list1);
- return pNode;
- }
- }
【三】相交链表
160. 相交链表
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
图示两个链表在节点 c1 开始相交：
题目数据 保证 整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构 。
自定义评测：
评测系统 的输入如下（你设计的程序 不适用 此输入）：
intersectVal- 相交的起始节点的值。如果不存在相交节点，这一值为0listA- 第一个链表listB- 第二个链表skipA- 在listA中（从头节点开始）跳到交叉节点的节点数skipB- 在listB中（从头节点开始）跳到交叉节点的节点数
评测系统将根据这些输入创建链式数据结构，并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点，那么你的解决方案将被 视作正确答案 。
示例 1：
输入：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 中第四个节点) 在内存中指向相同的位置。
示例 2：
输入：intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Intersected at '2'
解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [1,9,1,2,4]，链表 B 为 [3,2,4]。
在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。
示例 3：
输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2 输出：null 解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。 由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。 这两个链表不相交，因此返回 null 。
提示：
listA中节点数目为mlistB中节点数目为n1 <= m, n <= 3 * 1041 <= Node.val <= 1050 <= skipA <= m0 <= skipB <= n- 如果
listA和listB没有交点，intersectVal为0 - 如果
listA和listB有交点，intersectVal == listA[skipA] == listB[skipB]
进阶：你能否设计一个时间复杂度 O(m + n) 、仅用 O(1) 内存的解决方案？
【解法一】哈希解法：新建一个HashSet<ListNode>的集合，先遍历listA链表，把元素存储进去到set集合里面，再遍历listB链表，在遍历B链表的时候，如果set集合里包含有相同的元素，则返回该节点结束遍历，否则遍历完未匹配则返回null。
- public class Solution {
- public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
- if (headA == null || headB == null) {
- return null;
- }
- Set<ListNode> dataNode = HashSet<ListNode>();
- ListNode temp = headA;
- while(temp != null ){
- dataNode.add(temp);
- temp = temp.next;
- }
- temp = headB;
- while(temp != null ){
- if(dataNode.contains(temp)){
- return temp;
- }
- temp = temp.next;
- }
- return null;
- }
【解法二】双指针法：分别定义p1和p2两个指针指向headA和headB，同时移动p1和p2，当p1走到末尾节点时，next指向空，这时把p1指向p2的头结点，继续向前移动指针；当p2走到末尾节点时，next指向空，这时把p2指向p1的头节点，继续向前移动指针；当p1=p2时，这时就到了两个链表相交的地方，返回相交的节点即可。否则没有相交返回null。
- public class Solution {
- public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
- if (headA == null || headB == null) {
- return null;
- }
- ListNode p1 = headA;
- ListNode p2 = headB;
- while(p1 != p2 ){
- if(p1 == null){
- p1 = headB;
- }else{
- p1 = p1.next;
- }
-
- if(p2 == null){
- p2 = headA;
- }else{
- p2 = p2.next;
- }
- }
- return p1;
- }
- }
【四】反转链表
206. 反转链表
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
示例 1：
输入：head = [1,2,3,4,5] 输出：[5,4,3,2,1]
示例 2：
输入：head = [1,2] 输出：[2,1]
示例 3：
输入：head = [] 输出：[]
提示：
- 链表中节点的数目范围是
[0, 5000] -5000 <= Node.val <= 5000
进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？
【解法一】递归法：链表反转操作符合递归的条件：大问题可以拆解为相同的无数个小问题，小问题相加累计结束就是大问题；递归终止条件，当链表为空或者链表只要一个元素时，直接返回该链表。定义一个用来返回的链表，并且以递归调用（节点的下个节点next）形式；递归的逻辑，用节点head为例需要反转把指针调转表示为head.next.next（原来指向下下个节点）仍然指回来指向自己head，这样指针就反转了；最后要把head的头结点也就是反转后的头结点的下个节点next置为null（防止出现环）。
- class Solution {
- public ListNode reverseList(ListNode head) {
- //递归解法
- //1.递归终止条件
- if(head == null || head.next == null){
- return head;
- }
- ListNode p = reverseList(head.next);
- head.next.next = head;
- head.next = null;
- return p;
- }
【解法二】指针法：新建一个prev链表用于存储返回结果得到链表，新建一个curr链表指向head链表用来遍历的链表，遍历链表curr当链表不为空时，把链表当前的下一个节点next保存下来，把当前节点的下一节点next指针指向prev ，把prev设置为当前节点curr（相当于开始移动指针），把当前节点curr设置为next节点。循环遍历链表直至结束，即把原链表反转了。
- class Solution {
- public ListNode reverseList(ListNode head) {
- ListNode prev = null;
- ListNode curr = head;
- while(curr != null){
- ListNode next = curr.next;
- curr.next = prev;
- prev = curr;
- curr = next;
- }
- return prev ;
- }
- }
【五】回文链表
234. 回文链表
给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
示例 1：
输入：head = [1,2,2,1] 输出：true
示例 2：
输入：head = [1,2] 输出：false
提示：
- 链表中节点数目在范围
[1, 105]内 0 <= Node.val <= 9
进阶：你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
【解法一】数组+双指针法：先用数组把链表的元素值存储起来，最后再用双指针头指针从前到后开始移动，尾指针从后往前开始移动，每次移动2个指针直至遍历完链表元素值都相等则判断是回文链表，否则不是回文链表。
- class Solution {
- public boolean isPalindrome(ListNode head) {
- List<Integer> dataList = new ArrayList<Integer>();
- while(head != null ){
- dataList.add(head.val);
- head = head.next;
- }
- int p1 = 0;
- int p2 = dataList.size()-1;
- while(p1<p2){ //双指针不用循环，条件判断头尾指针相等时结束
- if(!dataList.get(p1).equal(dataList.get(p2))){
- return fasle;
- }
- p1++;
- p2--;
- }
- return true;
- }
【解法二】快慢指针法：先获取链表的前半部分，返回获得前半部分链表的最后一个元素，再反转后半部分链表（参数为前半部分链表的next节点），遍历反转后的后半部分链表，遍历完反转后的后半部分链表后，比较该反转后的后半部分链表元素与题干入参的链表head中的元素，都相等则判断是回文链表，否则不是。先获取链表的前半部分：快慢指针获取，快指针移动2个节点，慢指针移动1一个节点，当快指针到达末尾时，慢指针刚好走到链表的一半的位置。
反转后半部分链表：参考【三】
- class Solution {
- public boolean isPalindrome(ListNode head) {
- if(head == null){
- return true;
- }
- //获取到前半部分链表的元素(注意，这时链表指向前半部分最后一个节点)
- ListNode firstHalfNode = reverseHalf(head) );
- //反转后半部分链表，从前半部分的最后一个节点得到next节点开始
- ListNode reverseHalfNode = reverseNode(firstHalfNode.next) );
-
- //遍历反转后的后半部分链表，遍历完所有反转的后半部分链表，所有元素都相等表示属于回文链表
- ListNode temp = head;
- while(reverseHalfNode != null){
- if(temp.val != reverseHalfNode.val){
- return false;
- }
- reverseHalfNode = reverseHalfNode.next;
- temp = temp.next;
- }
- return true;
- }
- //1.通过快慢指针法获取前半部分的链表
- public ListNode getFirstHalf(ListNode head){
- ListNode fast = head;
- ListNode slow = head;
- while(fast != null && fast.next != null){
- fast = fast.next.next;
- slow = slow.next;
- }
- return slow;
- }
- //2.反转前半部分的链表元素
- public ListNode reverseNode((ListNode head){
- ListNode prev = null;
- ListNode curr = head;
- while(curr != null){
- ListNode next = curr.next;
- curr.next = prev;
- prev = curr;
- curr = next;
- }
- return prev;
- }
- }
【六】环形链表
141. 环形链表
示例 1：
输入：head = [3,2,0,-4], pos = 1 输出：true 解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：head = [1,2], pos = 0 输出：true 解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1 输出：false 解释：链表中没有环。
提示：
- 链表中节点的数目范围是
[0, 104] -105 <= Node.val <= 105pos为-1或者链表中的一个 有效索引 。
进阶：你能用 O(1)（即，常量）内存解决此问题吗？
给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ，则返回 true 。 否则，返回 false 。
【解法一】哈希法：
新建一个以ListNode为数据类型的Set集合，遍历链表并把链表的节点存储在Set集合里面，如果在遍历的过程中发现Set集合含有某个节点，在判断为环形链表。
- public class Solution {
- public boolean hasCycle(ListNode head) {
- while(head == null || head.next == null){
- return false;
- }
- Set<ListNode> dataNode = new HashSet<ListNode>();
- ListNode temp = head;
- while(temp != null){
- if(dataNode.contains(temp)){
- return true;
- }
- dataNode.add(temp);
- temp = temp.next;
- }
- return false;
- }
- }
【解法二】快慢指针法：
也称为龟兔赛跑法，fast的指针在head.next处，slow的指针在head处，同时移动fast指针和slow指针，fast指针移动2个节点每次，slow移动1个节点每次，当fast指针和slow指针遍历完链表后，fast和slow也没有相等，则表示该链表不是环形链表（注意：起始时把fast置为head.next而不是head是假设在head之前两个节点开始移动，这样才能进入while循环）。
- public class Solution {
- public boolean hasCycle(ListNode head) {
- while(head == null || head.next == null){
- return false;
- }
- ListNode fast = head.next;
- ListNode slow = head;
- while(fast != slow){
- if(fast == null || fast.next == null){
- return false;
- }
- fast = fast.next.next;
- slow = slow.next;
- }
- return true;
- }
- }
快慢指针简化：
快慢指针同时在head位置处，while循环终止条件是当fast移动至链表末尾还没有发现快慢指针相碰则返回false
- public class Solution {
- public boolean hasCycle(ListNode head) {
- while(head == null || head.next == null){
- return false;
- }
- ListNode fast = head,slow = head;
- while(fast != null && fast.next != null){
- if(fast == slow ){
- return true;
- }
- fast = fast.next.next;
- slow = slow.next;
- }
- return false;
- }
- }
【七】总结
关于链表的常用解法，有：快慢指针法，递归法，哈希法，迭代法。拿到题目先分析题型场景适用于哪个算法，找到对应算法后再思考解题逻辑，从而一步一步写出对应的题解的代码来。
如果是求环相关的可以使用快慢指针法，如果是求反转链表可以使用递归和迭代，如果是求合并链表可以用迭代法（新建链表头-1开始），如果是求回文链表可以使用数组+双指针法，如果是求相交链表，可以用双指针和哈希法（分别遍历2个链表，有相同节点则为相交）。
我是程序大视界，坚持原创技术博客分享。
注：如果本篇博客有任何纰漏和建议，欢迎私信或评论留言！
文章持续更新，可以VX搜索「 程序大视界 」第一时间阅读，回复【资料】免费领取学习资料，添加博主VX好友，进群交流获取大厂面试完整考点，欢迎Star。
