LeetCode 面试题 02.08. 环路检测

Categories:

题目描述
思路分析
1. 解法一：快慢指针（推荐）
相似题目

题目描述

✅ 面试题 02.08. 环路检测

思路分析

解法一：快慢指针（推荐）

核心思路：

使用快慢指针检测是否有环，若相遇则存在环。

令一个指针回到头节点，两个指针同步前进，再次相遇点即为入环点。

这是环形链表经典结论：相遇后同步走距离为入环点。

复杂度分析：

时间复杂度：O(n)，其中 n 表示链表长度。

空间复杂度：O(1)，仅使用常数额外空间。

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                ListNode p = head;
                while (p != slow) {
                    p = p.next;
                    slow = slow.next;
                }
                return p;
            }
        }

        return null;
    }
}

func detectCycle(head *ListNode) *ListNode {
	slow, fast := head, head

	for fast != nil && fast.Next != nil {
		slow = slow.Next
		fast = fast.Next.Next
		if slow == fast {
			p := head
			for p != slow {
				p = p.Next
				slow = slow.Next
			}
			return p
		}
	}

	return nil
}

相似题目

题目	难度	考察点
142. 环形链表 II	中等	快慢指针
141. 环形链表	简单	快慢指针
160. 相交链表	简单	双指针
234. 回文链表	简单	链表操作
876. 链表的中间结点	简单	快慢指针

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2024/44966011