代码随想录-链表 | 142环形链表

LeetCode 142-环形链表
- 解题思路
- 代码
- 复杂度
- 难点
- 总结

LeetCode 142-环形链表

题目链接

题目描述

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

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改链表。

解题思路

判断：

可用快慢指针法。分别定义 fast 和 slow 指针。都从头节点出发，fast 指针每次移动两个节点，slow 指针每次移动一个节点。

题目涉及两个步骤：

判断是否有环：fast 指针与 slow 指针相遇，则有环。
找到环的入口：另设两个指针，一个从头节点出发，另一个从相遇节点出发，每次都只移动一个节点，这两个指针相遇时即为环的入口。

代码

/**
 * 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 fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                ListNode index1 = head;
                ListNode index2 = fast;
                while (index1 != index2) {
                    index1 = index1.next;
                    index2 = index2.next;
                }
                return index1;
            }
        }
        return null;
    }
}