LeetCode 142. Linked List Cycle II (Tag:LinkedList)
LeetCode 142. Linked List Cycle II (Tag:LinkedList)
用户7447819
发布于 2021-07-23 11:26:47
发布于 2021-07-23 11:26:47
代码可运行
运行总次数：0
代码可运行
1. 问题描述
Given a linked list, return the node where the cycle begins. If there is no cycle, return null.
To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list. 翻译过来就是找到链表中的环，并返回环起点的节点。
2. 解题思路
如图所示，蓝色圈圈为环的起始点，红色圈圈为快，慢节点第一次相遇的地方。
- 第一次相遇的时候，slowNode走了 x1 + x2
- fastNode走了 x1 + x2 + x3 + x2
- 因为是第一次相遇，则fastNdoe走的长度是slowNode的2倍， 因此有x1 + x2 + x3 + x2 = 2(x1 + x2)
- 因此x1 = x3
- 那么从第一次快慢节点相遇开始，定义一个指向头节点的newNode，newNode 和 slowNode 每次前进一步，则它们必然在环的开始出相遇。
- 返回此时相遇的节点。
3. 代码
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/public class Solution {
public ListNode detectCycle(ListNode head) {
if(head == null || head.next == null) {
return null;
}
ListNode fastNode = head;
ListNode slowNode = head;
while(fastNode != null && fastNode.next != null) {
fastNode = fastNode.next.next;
slowNode = slowNode.next;
if(fastNode == slowNode){
ListNode newNode = head;
while(slowNode != newNode){
newNode = newNode.next;
slowNode = slowNode.next;
}
return slowNode;
}
}
return null;
}
}本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2019-01-24，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
