Leetcode 142. 环形链表II(Linked list cycle ii)

Ahci / 2023-08-19 / 原文

题目链接

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

如果链表中有某个节点, 可以通过连续跟踪next指针再次到达, 则链表中存在环. 为了表示给定链表中的环, 评测系统内部使用整数pos来表示链表尾连接到链表中的位置(索引从 0 开始). 如果pos是-1, 则在该链表中没有环.

注意: pos不作为参数进行传递, 仅仅是为了标识链表的实际情况. 不允许修改链表。

示例 1:

输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2:

输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。

提示:

链表中节点的数目范围在范围 [0, 104] 内
-105 <= Node.val <= 105
pos 的值为 -1 或者链表中的一个有效索引

思路

这道题首先想到的方法是使用Set去重来判断是否有环以及环的入口在哪个位置.

第二种方法是双指针法(快慢指针), 设置两个指针(slow and fast), slow指针每次前进一个节点, fast指针每次前进两个节点, 只要链表中有环, 它们就一定会相遇.

在这道题中的问题是如何确定环的入口. 可以将链表分为三个部分, 分别是从头节点到环入口的节点数x, 从环入口到fast指针和slow指针相遇的节点数为y, 从相遇节点到环入口的节点数z.

这样相遇时, slow指针走过的节点数为x + y, fast指针走过的节点数为x + y + n(y + z), 这里的n指的是fast指针走了n圈才遇到slow指针, (y + z)表示一个圈内的节点数.

由于fast一次走两个节点, slow一次走一个节点, 所以fast走过的节点数 == slow走过的节点数 * 2

也就是: (x + y) * 2 = x + y + n(y + z), 简化后为x = n(y + z) - y, 最后得到x = (n - 1) * (y + z) + z

由于fast至少走一圈才可以遇到slow指针, 所以n必定大于等于1. 当n == 1时, 公式化简为x = z

也就是从头节点出发一个指针, 从相遇节点出发一个指针, 两指针每次走一个节点, 相遇处即为环形入口节点.

代码实现

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) {
        if(head == null) {
            return null;
        }

        ListNode temp = head;
        Set<ListNode> set = new HashSet<ListNode>();

        while(temp != null) {
            if(set.contains(temp)) {
                return temp;
            } else {
                set.add(temp);
            }
            temp = temp.next;
        }

        return null;
    }
}

快慢指针:

/**
 * 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 slow = head;
        ListNode fast = head;

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

            if(slow == fast) {
                ListNode tempNode1 = fast;
                ListNode tempNode2 = head;

                while(tempNode1 != tempNode2) {
                    tempNode1 = tempNode1.next;
                    tempNode2 = tempNode2.next;
                }

                return tempNode1;
            }
        }

        return null;
    }
}