力扣 - 142. 环形链表 II

题目
思路1
- 代码实现
思路2
- 代码实现

题目

给定一个链表，返回链表开始入环的第一个节点。如果链表无环，则返回 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

解释：链表中没有环。

思路1

利用哈希表HashSet，保存访问过的路径，如果未访问过，就add添加且返回true，如果已存在再添加的话就会返回该结点，而且该结点就是他们重合的结点，否则返回null

代码实现

import java.util.HashSet;

public class Solution {

    public ListNode detectCycle(ListNode head) {

        //利用哈希表不重复元素的特性来存储结点判断是否存在环

        HashSet<ListNode> set = new HashSet<>();

        //只要没到头且还没重合就一直循环

        while (head != null) {

            if (!set.add(head)) {

                return head;

            }

            head = head.next;

        }

        //到末尾还是没有重合的话就是返回null

        return null;

    }

}

思路2

我们可以利用快慢指针，慢指针每次移动一个，快指针每次移动两个，如果确实存在环的话，最终一定会重合的
如果快指针最后为null，肯定是到末尾了，就没有环
我们假设头结点到重合的结点这段长度为a，重合的结点到相遇的结点为b，环的剩下部分为c
- 由于再相同的时间内，fast的速度是low的两倍，而low走的路程为a+b，fast为low的两倍那么路程应该是2(a+b)
- 由题分析可得，fast走过的长度为a+b+c+b
- 可得等式：a+b+c+b = 2(a+b) ，得到c = a
- 所以，我们可以等到相遇的时候再创建一个指向head的指针，同时以相同的速度向前移动，等到相遇的时候就是我们要的环重合的结点

代码实现

import java.util.HashSet;

public class Solution {

    public ListNode detectCycle(ListNode head) {

        //定义快慢指针

        ListNode low = head;

        ListNode fast = head;

        //若为空或者只有一个元素时候就是无环的

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

            low = low.next;

            fast = fast.next.next;

            //如果快慢指针重合就代表存在环，然后开始寻找重合点

            if (fast == low) {

                //定义一个pre指针指向head，让pre和low同时移动，等到重合时就是指向重合的点

                ListNode pre = head;

                while (pre != low) {

                    pre = pre.next;

                    low = low.next;

                }

                return pre;

            }

        }

        return null;

    }

}

巴特西

力扣 - 142. 环形链表 II

题目

思路1

代码实现

思路2

代码实现

最新文章

热门文章