2022.11.24环形链表21 力扣题142:环形链表2

1 力扣题142:环形链表2

1.1 题目描述

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

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

1.2 思路分析

1.2.1 快慢指针

注意，这一题需要用到假设和证明，也就是会触及到算法最核心的那部分思想，归纳、逆向。首先定义三段距离，头结点到环初始节点距离a，环初始节点到相遇节点距离b，相遇节点经过一圈到环初始节点距离c。之后利用快节点速度是慢节点速度的两倍可以得到一个等式，对等式进行化简可以得到a=c的等式，这个等式意味着从头结点到环初始节点与相遇节点到环初始节点距离相等，故最后只需在创造一个头结点，与相遇节点一起移动，相遇后的节点即为环初始节点

1.3 代码实现

1.3.1 快慢指针

public ListNode detectCycle(ListNode head) {
        if (head==null || head.next==null) 
            return null;
        ListNode fp = head;
        ListNode sp = head;
        while (sp!=null) {
            fp = fp.next;
            if (sp.next!=null)
                sp = sp.next.next;
            else
                return null;
            if (fp==sp) {
                ListNode firstNode = head;
                while (fp!=firstNode) {
                    fp = fp.next;
                    firstNode = firstNode.next;
                }
                return fp;
            }
        }
        return null;
    }

最后

以上就是顺利汽车为你收集整理的2022.11.24环形链表21 力扣题142:环形链表2的全部内容，希望文章能够帮你解决2022.11.24环形链表21 力扣题142:环形链表2所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。