企业免费自助建站平台,照片做成视频的软件,公司查询网站查询系统,湖南省建设信息网【算法系列-链表】链表相交环形链表 文章目录 【算法系列-链表】链表相交环形链表1. 链表相交1.1 思路分析#x1f3af;1.2 解题过程#x1f3ac;1.3 代码示例#x1f330; 2. 环形链表II2.1 思路分析#x1f3af;2.2 代码示例#x1f330; 1. 链表相交
【题目…【算法系列-链表】链表相交环形链表 文章目录 【算法系列-链表】链表相交环形链表1. 链表相交1.1 思路分析1.2 解题过程1.3 代码示例 2. 环形链表II2.1 思路分析2.2 代码示例 1. 链表相交
【题目链接】 LeetCode 面试题 02.07.链表相交
1.1 思路分析
这道题最直接的思路就是找到两条链表中最长的那条然后定义一个指针从这条最长链表的头节点开始遍历 遍历两条链表的长度的差值后此时定义两个指针开始同步各自遍历两条链表找到相同的结点则返回直到 找到节点 或 其中一个链表被遍历完则退出循环返回null
1.2 解题过程 先定义指针 cur1 和 cur2 用来分别遍历两条链表分别计算出两条链表各自的长度 len1、len2 之后进行判断选出最长的那条链表进行循环遍历 从头节点开始让指针走到与短链表头节点平行的位置(链表长度不等时长链表超出短链表前面的部分是不会相交的所以要排除掉) 之后从这个位置进行同步遍历直到找到交点 或 其中一条链表已经遍历完退出循环返回结果 1.3 代码示例
public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {ListNode cur1 headA;ListNode cur2 headB;int len1 0, len2 0;while (cur1 ! null) {len1;cur1 cur1.next;}while (cur2 ! null) {len2;cur2 cur2.next;}cur1 headA;cur2 headB;if (len1 len2) {for (int i 0;i len1 - len2;i) {cur1 cur1.next;}}else {for (int i 0;i len2 - len1;i) {cur2 cur2.next;}}while (cur1 ! null cur2 ! null) {if (cur1 cur2) {return cur1;}cur1 cur1.next;cur2 cur2.next;}return null;}
}这里还有一种解题思路 定义两个指针让它们对每条链表都依次进行遍历即 cur1遍历完链表A后就遍历链表Bcur2遍历完链表B后就遍历链表A直到二者相遇返回的cur1就是交点(若 cur1 与 cur2 都为空也能退出循环并返回)代码可以说非常简洁优雅如下 public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {ListNode cur1 headA;ListNode cur2 headB;while (cur1 ! cur2) {cur1 (cur1 ! null ? cur1.next : headB);cur2 (cur2 ! null ? cur2.next : headA);}return cur1;}
}2. 环形链表II
【题目链接】LeetCode 142 环形链表II
2.1 思路分析 这道题可以利用快慢指针来解决问题同时需要解决两个关键性的问题 是否有环有环快慢指针相遇时来找入口 如何判断是否有环可以通过遍历快慢指针来找
当 fast ! null fast.next ! null 时让fast走两步slow走一步这样循环遍历下去若存在环则fast指针一定能够追上slow指针(前提是fast每次只走两步若fast走三步则可能会跳过slow) fast走两步slow走一步最后能够在环里相遇 快慢指针相遇后接下来就能够来找入口了这里涉及到了一点数学知识(换算)
设 从头节点开始到入口的长度为 x设 从入口节点到两个指针相遇的位置节点的距离为 y设 相遇节点到环形入口的距离为 z; 在快慢指针相遇时: fast指针走过的长度为 x y n * (y z)n为走过的圈数且大于等于1 slow指针走过的长度为 x y;
且快指针每次走的长度为慢指针的两倍即 2 * (x y) x y n * (y z)两边同时消掉一个 x y则:
x y n * (y z) x n * (y z) - y;此时消掉一个(y z)来与y进行抵消可以得到x (n - 1)(y z) z;
且n 1所以当n等于1时x z所以 从头节点开始到入口的长度 相遇节点到环形入口的距离
得到上述结论后通过定义两个指针分别从头节点和快慢指针相遇节点开始遍历 直到二者相遇将此时的位置返回即可 2.2 代码示例
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 index1 fast;ListNode index2 head;while (index1 ! index2) {index1 index1.next;index2 index2.next;}return index1;}}return null;}
}以上便是对链表相交环形链表II类型题的介绍了后续还会继续分享其它算法系列内容如果这些内容对大家有帮助的话请给一个三连关注吧( •̀ ω •́ )✧( •̀ ω •́ )✧✨
