leetcode142

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

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

这里有一个关键点是,
快指针步长是慢指针两倍,时间相同,所以距离也是两倍
快指针走的距离是慢指针的两倍, 得出来快指针y=L,接下来就让slow和head同时走,相遇则到头结点。

func detectCycle(head *ListNode) *ListNode {
    fast := head
    slow := head
    for fast!=nil&&fast.Next!=nil{
        fast = fast.Next.Next
        slow = slow.Next
        if fast==slow&&fast!=head{
            for slow!=head{
                slow = slow.Next
                head = head.Next
            }
            return slow
        }
    }
    return nil
}
分类: 算法

站点统计

  • 文章总数:309 篇
  • 分类总数:19 个
  • 标签总数:190 个
  • 运行天数:975 天
  • 访问总数:72766 人次

浙公网安备33011302000604

辽ICP备20003309号