【LeetCode】环形链表 II Java 题解

2021 年 11 月 12 日
本文字数：889 字
阅读完需：约 3 分钟

题目描述

给定一个链表，返回链表开始入环的第一个节点。如果链表无环，则返回 null。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。

说明：不允许修改给定的链表。

进阶：

你是否可以使用 O(1) 空间解决此题？

示例 1：
输入：head = [3,2,0,-4], pos = 1输出：返回索引为 1 的链表节点解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：head = [1,2], pos = 0输出：返回索引为 0 的链表节点解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1输出：返回 null解释：链表中没有环。
来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/linked-list-cycle-ii著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

思路分析

今天的算法每日一题链表题目。具体是找链表开始入环的第一个节点。如果链表无环，则返回 null。我们可以转化为判断链表是否有环，简而言之，就是节点有没重复出现过。
首先，我们采用朴素算法，使用 hashSet 来做，记录出现的每个节点，如果一个结点出现两次，即为有环，第一次出现重复的节点，即为入环的第一个节点。

通过代码

hashSet 解法

/** * 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 pos = head;        Set<ListNode> visited = new HashSet<>();        while (pos != null) {            if (visited.contains(pos)) {                return pos;            } else {                visited.add(pos);            }            pos = pos.next;        }        return null;    }}