软装设计素材网站/爱站关键词

目录

1 题目描述

对于一个给定的链表，返回环的入口节点，如果没有环，返回null

拓展：

你能给出不利用额外空间的解法么？

2 解题(Java)

/**

* 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) {

ListNode fast = head;

ListNode slow = head;

while(fast!= null && fast.next != null){

fast = fast.next.next;//利用快慢指针找相遇点

slow = slow.next;

if(slow == fast){//找到相遇点后令快指针重新指向链表起始位置，并设置和慢指针相同的速度

fast = head;

while(fast != slow){//再次相遇即为环的入口结点

slow = slow.next;

fast = fast.next;

}

return fast;

}

}

return null;

}

}

3 复杂性分析

时间复杂度O(N)：线性遍历链表中的各个结点；

空间复杂度O(1)：快慢指针占用常数大小的额外空间；

标签：slow,ListNode,中环,fast,next,链表,牛客,null

来源： https://blog.csdn.net/sc179/article/details/114482832