链表|[java刷算法]牛客—剑指offer链表有环的入口、反转链表、合并排序链表 java|面试|数据结构|算法

?♂?个人主页：杯咖啡

进步是今天的活动，明天的保证！

?目前正在学习：SSM框架,算法刷题

本文收录专栏： java刷算法牛客—剑指offer

牛客网，刷算法过面试的神级网站，用牛客你也牛。免费注册和我一起学习刷题

希望大家多多支持一起进步呀！

The man who fears losing has already lost.
怕输的人已经输了。 - 《权力的游戏》

?今日三剑 JZ23 链表中环的入口结点
JZ24 反转链表
JZ25 合并两个排序的链表

文章目录

?今日三剑
JZ23 链表中环的入口结点
- 题目描述
- 思路详解
- 代码与结果
JZ24 反转链表
- 题目描述
- 思路详解
- 代码与结果
JZ25 合并两个排序的链表
- 题目描述
- 思路详解
- 代码与结果

JZ23 链表中环的入口结点题目描述

链表|[java刷算法]牛客—剑指offer链表有环的入口、反转链表、合并排序链表

文章图片

文章图片

思路详解

本题采用快慢指针的思路解题。
对于判断有没有环，利用环没有末尾NULL，后半部分一定是环，然后快慢双指针相遇就代表有环。
那我们现在假定已经是一个有环的链表了，那么这个链表中怎么找到环的入口呢？在慢指针进入链表环之前，快指针已经进入了环，且在里面循环，这才能在慢指针进入环之后，快指针追到了慢指针，不妨假设快指针在环中走了n圈，慢指针在环中走了m圈，它们才相遇，而进入环之前的距离为x，环入口到相遇点的距离为y，相遇点到环入口的距离为z。快指针一共走了x+n(y+z)+y步，慢指针一共走了x+m(y+z)+y，这个时候快指针走的倍数是慢指针的两倍，则x+n(y+z)+y=2(x+m(y+z)+y)，这时候x+y=(n?2m)(y+z)。因为环的大小是y+z，说明从链表头经过环入口到达相遇地方经过的距离等于整数倍环的大小：那我们从头开始遍历到相遇位置，和从相遇位置开始在环中遍历，会使用相同的步数，而双方最后都会经过入口到相遇位置这y个节点，那说明这y个节点它们就是重叠遍历的，那它们从入口位置就相遇。

代码与结果

import java.util.*; /* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } } */ public class Solution { //判断有没有环，返回相遇的地方 public ListNode hasCycle(ListNode head) { //先判断链表为空的情况 if(head == null) return null; //快慢双指针 ListNode fast = head; ListNode slow = head; //如果没环快指针会先到链表尾 while(fast != null && fast.next != null){ //快指针移动两步 fast = fast.next.next; //慢指针移动一步 slow = slow.next; //相遇则有环，返回相遇的位置 if(fast == slow) return slow; } //到末尾说明没有环，返回null return null; }public ListNode EntryNodeOfLoop(ListNode pHead) { ListNode slow = hasCycle(pHead); //没有环 if(slow == null) return null; //快指针回到表头 ListNode fast = pHead; //再次相遇即是环入口 while(fast != slow){ fast = fast.next; slow = slow.next; } return slow; } }

【链表|[java刷算法]牛客—剑指offer链表有环的入口、反转链表、合并排序链表】

文章图片

JZ24 反转链表题目描述

文章图片

文章图片

思路详解

最简单的一种方式就是使用栈，因为栈是先进后出的。实现原理就是把链表节点一个个入栈，当全部入栈完之后再一个个出栈，出栈的时候在把出栈的结点串成一个新的链表。

代码与结果

import java.util.*; /* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } }*/ public class Solution { public ListNode ReverseList(ListNode head) { Stack stack= new Stack<>(); //把链表节点全部摘掉放到栈中 while (head != null) { stack.push(head); head = head.next; } if (stack.isEmpty()) return null; ListNode node = stack.pop(); ListNode dummy = node; //栈中的结点全部出栈，然后重新连成一个新的链表 while (!stack.isEmpty()) { ListNode tempNode = stack.pop(); node.next = tempNode; node = node.next; } //最后一个结点就是反转前的头结点，一定要让他的next //等于空，否则会构成环 node.next = null; return dummy; } }

文章图片

JZ25 合并两个排序的链表题目描述

文章图片

文章图片

思路详解

从头结点开始考虑，比较两表头结点的值，值较小的list的头结点后面接merge好的链表（进入递归了）；
若两链表有一个为空，返回非空链表，递归结束；
当前层不考虑下一层的细节，当前层较小的结点接上该结点的next与另一结点merge好的表头就ok了；
每层返回选定的较小结点就ok；

终止条件：两链表其中一个为空时，返回另一个链表；
当前递归内容：若list1.val <= list2.val 将较小的list1.next与merge后的表头连接，即list1.next = Merge(list1.next,list2); list2.val较大时同理；
每次的返回值：排序好的链表头；

代码与结果

import java.util.*; /* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } }*/ public class Solution { public ListNode Merge(ListNode list1,ListNode list2) { if(list1==null){ return list2; } else if(list2==null){ return list1; } if(list2.val>list1.val){ list1.next = Merge(list1.next,list2); return list1; } else{ list2.next = Merge(list1,list2.next); return list2; } } }

文章图片

原创不易，还希望各位大佬支持一下 \textcolor{blue}{原创不易，还希望各位大佬支持一下} 原创不易，还希望各位大佬支持一下

点赞，你的认可是我创作的动力！ \textcolor{green}{点赞，你的认可是我创作的动力！} 点赞，你的认可是我创作的动力！

收藏，你的青睐是我努力的方向！ \textcolor{green}{收藏，你的青睐是我努力的方向！} 收藏，你的青睐是我努力的方向！

评论，你的意见是我进步的财富！ \textcolor{green}{评论，你的意见是我进步的财富！} 评论，你的意见是我进步的财富！