美文网首页
leetcode 142. 环形链表 II

leetcode 142. 环形链表 II

作者: topshi | 来源:发表于2019-05-29 17:29 被阅读0次

题目描述

给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。
为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。
说明:不允许修改给定的链表。
相关话题: 链表、双指针    难度: 中等

示例 1:

示例 2:

示例 3:


进阶:
你是否可以不用额外空间解决此题?
思路:这道题需要先确定链表有环,方法同leetcode 141. 环形链表
  • 定义两个指针,慢指针slow和快指针fast,慢指针一次走一步,快指针一次走两步;
  • 当慢指针和快指针重合,即slow == fast,确定链表有环,此时慢指针slow回到链表头部,快指针fast和慢指针slow每次走一步,当慢指针和快指针再次重合,重合的节点就是环的入口节点。

证明:


如图,无环部分长度为 L,有环部分长度为R,第一次相遇指针离入环节点距离为C
假设t时刻,slowfast指针相遇,则

两式相减,t = (k_2 - k_1)R,可以看出slow指针和fast指针的距离为环长度的倍数,那么它们必定会在某个时刻相遇。
证明它们会相遇之后,我们反证法证明第二次相遇的位置就是环的入口节点。
已知它们t时刻会在入口节点相遇,

整理得,L = kR - C。可以理解为fast指针比slow指针领先了C步,kR-C看成fast指针退后C步出发,slow指针从链表头出发,刚好相差kR,也就是说slow走过L来到入口节点时,fast也在入口节点,不矛盾。

/**
 * 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 slow = head;
        ListNode fast = head;
        //slow一次走一步,fast一次走两步,如果相遇就是有环
        while(fast.next != null&&fast.next.next != null){
            slow = slow.next;
            fast = fast.next.next;
            //有环
            if(slow == fast){
                slow = head;//slow指针回到head
                //slow和fast变成每次走一步,相遇时就是入口节点
                while(slow != fast){
                    slow = slow.next;
                    fast = fast.next;
                }
                return slow;
            }
        }
        return null;
    }
}

相关文章

  • 获取有环单向列表环入口的结点(双指针法)

    LeetCode 141.环形链表 142.环形链表II 对题目不熟悉的同学,可以先刷下题,结合LeetCode上...

  • TOP100

    142. 环形链表 II[https://leetcode-cn.com/problems/linked-list...

  • LeetCode 142 环形链表 II Linked List

    有关链表的LeetCode做题笔记合集,Python实现 链表定义 142. 环形链表 II Linked Lis...

  • LeetCode:142. 环形链表 II

    问题链接 142. 环形链表 II[https://leetcode-cn.com/problems/linked...

  • 142. 环形链表 II

    题目地址(142. 环形链表 II) https://leetcode.cn/problems/linked-li...

  • 双指针

    一、双指针总结 1.1题目 快慢指针(主要解决链表中的问题) 141.环形链表 142.环形链表 II 876.链...

  • LeetCode 142. 环形链表 II

    142. 环形链表 II 给定一个链表,判断链表中是否有环。为了表示给定链表中的环,我们使用整数 pos 来表示链...

  • LeetCode 142. 环形链表 II

    给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。为了表示给定链表中的环,我们使用整数...

  • leetcode 142. 环形链表 II

    题目描述 给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。为了表示给定链表中的环,我...

  • 【LeetCode】142.环形链表II

    题目描述 142.环形链表 II 给定一个链表,返回链表开始入环的第一个节点。如果链表无环,则返回 null。为了...

网友评论

      本文标题:leetcode 142. 环形链表 II

      本文链接:https://www.haomeiwen.com/subject/lxyytctx.html