【算法系列-链表】链表相交 环形链表II

【算法系列-链表】链表相交&环形链表

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后就遍历链表B，cur2遍历完链表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 思路分析🎯

这道题可以利用快慢指针来解决问题，同时需要解决两个关键性的问题：

1. 是否有环
2. 有环快慢指针相遇时来找入口

如何判断是否有环，可以通过遍历快慢指针来找：

当 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类型题的介绍了！！后续还会继续分享其它算法系列内容，如果这些内容对大家有帮助的话请给一个三连关注吧💕( •̀ ω •́ )✧( •̀ ω •́ )✧✨