給定一個有環鏈表，實現一個算法返回環路的開頭節點。
有環鏈表的定義：在鏈表中某個節點的next元素指向在它前面出現過的節點，則表明該鏈表存在環路。

示例 1：

輸入：head = [3,2,0,-4], pos = 1
輸出：tail connects to node index 1
解釋：鏈表中有一個環，其尾部連接到第二個節點。

示例 2：

輸入：head = [1,2], pos = 0
輸出：tail connects to node index 0
解釋：鏈表中有一個環，其尾部連接到第一個節點。

示例 3：

輸入：head = [1], pos = -1
輸出：no cycle
解釋：鏈表中沒有環。

進階：
你是否可以不用額外空間解決此題？

1\檢測有沒有環，使用快慢指針slow和fast（一次走兩步）；
2\找位置，當找到環之后，slow從head出發，fast從相遇點出發，一次都走一步，再次相遇為環的入口點

/*** 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 slow = head, fast = head; while (fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;if (slow == fast) {break;}}if (fast == null || fast.next == null) {return null;}// slow從head開始，fast從相遇點開始，一步一步走再次相遇即為環入口slow = head;while (slow != fast) {slow = slow.next;fast = fast.next;}return slow;} }

?

總結

以上是生活随笔為你收集整理的leetcode面试题 02.08. 环路检测的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。