专栏首页freesan44LeetCode 142. 环形链表 II

LeetCode 142. 环形链表 II

题目

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

为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。

说明:不允许修改给定的链表。

示例 1:

输入:head = [3,2,0,-4], pos = 1
输出:tail connects to node index 1
解释:链表中有一个环,其尾部连接到第二个节点。
示例 2:

输入:head = [1,2], pos = 0
输出:tail connects to node index 0
解释:链表中有一个环,其尾部连接到第一个节点。
示例 3:

输入:head = [1], pos = -1
输出:no cycle
解释:链表中没有环。

进阶: 你是否可以不用额外空间解决此题?

解题思路

class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        # #存值做法
        # numsList = []
        # while head:
        #     if head in numsList:
        #         return head
        #     numsList.append(head)
        #     try:
        #         head = head.next
        #     except:
        #         return None
        # return None
        # 双指针双倍速度走向,当相遇的时候,慢指针再走n步,就走到链表循环入口,而n步也是从头部走到入口的部数
        left = right = head
        while right:
            try:
                left = left.next
                right = right.next.next
            except:
                return None
            if left == right:  # 相遇后,入口的也开始走了
                break
        right = head  # right指针回到表头重新走
        while left and right:
            if left == right:
                return left
            left = left.next
            right = right.next
        return None

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode 141. 环形链表

    为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。

    freesan44
  • LeetCode 125. 验证回文串

    freesan44
  • LeetCode 680. 验证回文字符串 Ⅱ

    freesan44
  • LeetCode 141. 环形链表

    为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。

    freesan44
  • 微信小程序_09 HTTPS

    标准模板 var util = require('../../utils/util.js') wx.request({ url: 'https://URL...

    酷走天涯
  • 【数据结构】单链表的增删改查

    单链表需要使用的函数指针操作小技巧计算单链表的长度创建单链表单链表插入数据单链表删除数据效率分析

    程序员周同学
  • 1、Spring注解之@RequestMapping

    @RequestMapping是一个用来处理请求地址映射的注解,可用于类或者方法上。用于类上,表示类中的所有响应请求的方法都是以该地址作为父路径。

    java乐园
  • Java高级特性——注解,这也许是最简单易懂的文章了

    博主在初学注解的时候看到网上的介绍大部分都是直接介绍用法或者功能,没有实际的应用场景,篇幅又很长导致学习的时候难以理解其意图,而且学完就忘QAQ。本篇文章中我将...

    lyb-geek
  • Java高级特性——注解,这也许是最简单易懂的文章了

    博主在初学注解的时候看到网上的介绍大部分都是直接介绍用法或者功能,没有实际的应用场景,篇幅又很长导致学习的时候难以理解其意图,而且学完就忘QAQ。本篇文章中我将...

    Java团长
  • React Native探索之组件的属性和状态

    在Android或者iOS开发中我们会用到很多控件,这些控件会有很多的属性、样式等等。同样的,React Native中的组件也有属性、样式和状态。

    用户1269200

扫码关注云+社区

领取腾讯云代金券