LeetCode142.环形链表II

LeetCode142.环形链表II

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

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

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

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

龟兔赛跑（快慢指针）法：

/** * @author mac * @date 2020/11/11-19:54 */public class t142_环形链表II { public ListNode detectCycle(ListNode head) { // 如果链表是null，或者只有一个就没有环，直接返回null if (head == null || head.next == null) { return null; } // 设置慢节点 ListNode i = head; // 设置快节点 ListNode j = head; // 循环遍历找重合点 while (true) { // 如果快指针遍历结束，证明没有环 if (j.next == null || j.next.next == null) { return null; } // 慢指针一次移动一位 i = i.next; // 快指针一次移动两位 j = j.next.next; // 如果快慢指针重合，证明有环 if (i == j) { break; } } // 将慢指针重新指向头结点 i = head; // j指针 位置不变 ，将i指针重新 指向链表头部节点 ；i和j同时每轮向前走n步； 此时f=0,s=nb； // 当i指针走到f=a步时，j指针走到步s=a+nb，此时 两指针重合，并同时指向链表环入口 。 // 重新循环，返回索引为 1 (pos = 1)的链表节点(链表环入口) while (i != j) { i = i.next; j = j.next; } return i; } /** * Definition for singly-linked list. */ class ListNode { int val; ListNode next; ListNode(int x) { val = x; next = null; } }}

二、哈希表法

public ListNode detectCycle(ListNode head) { // 如果链表是null，或者只有一个就没有环，直接返回null if (head == null || head.next == null) { return null; } // 创建一个空的Hash表 Set set = new HashSet(); ListNode i = head; // 从头节点开始遍历 while (i != null) { // set中如果存在就直接返回 if (set.contains(i)) { return i; } else { // 如果不存在，则add到hash表中 set.add(i); } i = i.next; } // 循环结束 return null; }

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。