剑指 链表环的入口

链表中环的入口结点

http://www.nowcoder.com/questionTerminal/253d2c59ec3e4bc68da16833f79a38e4

通过指针方法,设置快慢指针,快指针每次前进两个节点,慢指针每次前进一个节点,当他们第一次相遇后,证明链表中存在环,然后将快指针置为头指针,慢指针与快指针继续每次前进一个节点,当他们再次相遇,就是换的入口位置。如果快慢指针从不相遇,快指针会走到链表结尾,那么就不存在环。O(n)

快指针走了n(n >= 1)圈后与慢指针相遇,
固有:
2(A + B) = n(B+C)+B+A
A = nC+(n-1)B
A = C + (n-1)(C+B)
因为C+B为一圈的长度,所以用c, h两个指针从p点和head开始走,当h走完A时,c走过的路为C + (n-1)(C+B),即n圈+C,所以h和c的相遇点为q

图片说明

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def EntryNodeOfLoop(self, pHead):
        # write code here
        quick=slow=pHead
        if quick==None :
            return None
        while quick!=None and quick.next!=None:
            quick=quick.next.next
            slow=slow.next
            if quick==slow:
                quick=pHead
                while slow!=quick:
                    quick=quick.next
                    slow=slow.next
                return slow
        return None

使用数组来保存遍历过的节点,当遇到和先前节点一样的节点,那就是存在环,以及当前节点为环的入口。空间复杂度O(n) 时间复杂度O(n)

class Solution:
    def EntryNodeOfLoop(self, pHead):
        # write code here
        if pHead==None:
            return None
        l=pHead
        listnode=[]
        while l!=None:
            if l in listnode:
                return l
            listnode.append(l)
            l=l.next
        return None

注意!此信息未认证,请谨慎判断信息的真实性!

全部评论
空

相关内容推荐

头像
2022-12-20 00:05
门头沟学院_2023
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像 会员标识 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
2022-12-16 02:48
门头沟学院_2022
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
2022-12-22 16:33
重庆工商大学_2024
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
点赞 收藏 评论
分享

全站热榜

正在热议