环形链表 II(力扣142)(快慢指针)

简介: 环形链表

 题目描述:

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

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

不允许修改 链表。

示例 1:

image.gif编辑

输入:head = [3,2,0,-4], pos = 1

输出:返回索引为 1 的链表节点

解释:链表中有一个环,其尾部连接到第二个节点。


示例 2:

image.gif编辑

输入:head = [1,2], pos = 0

输出:返回索引为 0 的链表节点

解释:链表中有一个环,其尾部连接到第一个节点。


示例 3:

image.gif编辑

输入:head = [1], pos = -1

输出:返回 null

解释:链表中没有环。

提示:

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

    题解:

    image.gif编辑

    代码实现:

    public ListNode detectCycle(ListNode head) {
            // 结论 : 快慢指针相遇时,引入一个新的节点从链表头结点开始
            // 最终新节点一定会和慢指针在环的入口位置相遇
            ListNode low = head,fast = head;
            while (fast != null && fast.next != null) {
                low = low.next;
                fast = fast.next.next;
                if (low == fast) {
                    ListNode third = head;
                    while (third != low) {
                        low = low.next;
                        third = third.next;
                    }
                    return low;
                }
            }
            return null;
        }

    image.gif


    目录
    打赏
    0
    0
    1
    0
    15
    分享
    相关文章
    |
    3月前
    【力扣】-- 移除链表元素
    【力扣】-- 移除链表元素
    46 1
    |
    3月前
    Leetcode第21题(合并两个有序链表)
    这篇文章介绍了如何使用非递归和递归方法解决LeetCode第21题,即合并两个有序链表的问题。
    60 0
    Leetcode第21题(合并两个有序链表)
    |
    2月前
    |
    单链表题+数组题(快慢指针和左右指针)
    单链表题+数组题(快慢指针和左右指针)
    43 1
    |
    3月前
    LeetCode第二十四题(两两交换链表中的节点)
    这篇文章介绍了LeetCode第24题的解法,即如何通过使用三个指针(preNode, curNode, curNextNode)来两两交换链表中的节点,并提供了详细的代码实现。
    34 0
    LeetCode第二十四题(两两交换链表中的节点)
    |
    3月前
    Leetcode第十九题(删除链表的倒数第N个节点)
    LeetCode第19题要求删除链表的倒数第N个节点,可以通过快慢指针法在一次遍历中实现。
    50 0
    Leetcode第十九题(删除链表的倒数第N个节点)
    |
    3月前
    |
    力扣(LeetCode)数据结构练习题(3)------链表
    力扣(LeetCode)数据结构练习题(3)------链表
    112 0
    |
    3月前
    |
    一篇文章了解区分指针数组,数组指针,函数指针,链表。
    一篇文章了解区分指针数组,数组指针,函数指针,链表。
    30 0
    |
    3月前
    【LeetCode 10】142. 环形链表 II
    【LeetCode 10】142. 环形链表 II
    30 0
    |
    3月前
    【LeetCode 09】19 删除链表的倒数第 N 个结点
    【LeetCode 09】19 删除链表的倒数第 N 个结点
    22 0
    |
    3月前
    【LeetCode 08】206 反转链表
    【LeetCode 08】206 反转链表
    18 0