剑指Offer-链表中环的入口结点

it2022-05-06  5

题目描述

一个链表中包含环,请找出该链表的环的入口结点。

思路

思路一:

利用HashSet元素不能重复

思路二:

假设x为环前面的路程,a为环入口到相遇点的路程, c为环的长度

当快慢指针相遇的时候: 此时慢指针走的路程为Sslow = x + m * c + a

快指针走的路程为Sfast = x + n * c + a

2 Sslow = Sfast

2 * ( x + m * c + a ) = (x + n * c + a)

从而可以推导出: x = (n - 2 * m ) * c - a = (n - 2 * m -1 ) * c + c - a

即环前面的路程 = 数个环的长度(为可能为0) + c - a

什么是c - a?这是相遇点后,环后面部分的路程。

所以,我们可以让一个指针从起点A开始走,让一个指针从相遇点B开始继续往后走, 2个指针速度一样,

那么,当从原点的指针走到环入口点的时候(此时刚好走了x) 从相遇点开始走的那个指针也一定刚好到达环入口点。

所以两者会相遇,且恰好相遇在环的入口点。

代码实现

package LinkedList; import java.util.HashSet; /** * 链表中环的入口结点 * 一个链表中包含环,请找出该链表的环的入口结点。 */ public class Solution24 { /** * 假设x为环前面的路程,a为环入口到相遇点的路程, c为环的长度 * 当快慢指针相遇的时候: 此时慢指针走的路程为Sslow = x + m * c + a * 快指针走的路程为Sfast = x + n * c + a * 2 Sslow = Sfast * 2 * ( x + m*c + a ) = (x + n *c + a) * 从而可以推导出: x = (n - 2 * m )*c - a = (n - 2 *m -1 )*c + c - a * 即环前面的路程 = 数个环的长度(为可能为0) + c - a * 什么是c - a?这是相遇点后,环后面部分的路程。 * 所以,我们可以让一个指针从起点A开始走,让一个指针从相遇点B开始继续往后走, 2个指针速度一样, * 那么,当从原点的指针走到环入口点的时候(此时刚好走了x) 从相遇点开始走的那个指针也一定刚好到达环入口点。 * 所以两者会相遇,且恰好相遇在环的入口点。 * 时间复杂度:O(n) * 空间复杂度:O(1) * * @param pHead * @return */ public ListNode EntryNodeOfLoop_2(ListNode pHead) { if (pHead == null || pHead.next == null || pHead.next.next == null) return null; ListNode fast = pHead.next.next; ListNode slow = pHead.next; //先判断有没有环 while (fast != slow) { if (fast.next != null && fast.next.next != null) { fast = fast.next.next; slow = slow.next; } else { //没有环 return null; } } fast = pHead;//把fast指向头节点 //有环 while (fast != slow) { fast = fast.next; slow = slow.next; } return fast; } /** * 利用HashSet元素不能重复 * * @param pHead * @return */ public ListNode EntryNodeOfLoop(ListNode pHead) { HashSet<ListNode> hashSet = new HashSet<>(); while (pHead != null) { if (!hashSet.add(pHead)) { return pHead; } pHead = pHead.next; } return null; } public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } } }

转载于:https://www.cnblogs.com/wupeixuan/p/8623412.html

相关资源:数据结构—成绩单生成器

最新回复(0)