接外包,有相关需求的可以联系我:Telegram | Email

环形链表 II - 双指针

该文章创建(更新)于02/21/2022,请注意文章的时效性!

Description

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

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

Thought

双指针技巧,当快慢指针相遇时,其中一个再去头节点,此时快慢指针同步运行(1个step),再次相遇时就为我们需要的节点。不要被题干中的pos给引导了

Solution

  • Accepted
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        fast = head
        slow = head


        while(fast != None and slow !=None):
            # 无环的情况
            if(fast.next == None): 
                return None

            fast = fast.next.next
            slow = slow.next

            if(fast == slow):
                slow = head
                while(fast != slow):
                    slow = slow.next
                    fast = fast.next
                return slow
                break
  • Time Limit Exceeded,有点疑惑为啥单独搞一个ListNode就不行呢?
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    def hasCycle(self, head:ListNode):

        # 环状链表的构造
        listN = ListNode(head[0])
        tmp = listN
        cir = listN
        # pos 为-1时则无环
        pos = 1
        for m in range(head.__len__()):
            listN.next = ListNode(head[m])
            listN = listN.next
            # 有环状的情况
            # 这中忽略了pos为0的情况
            if m == pos:
                cir = listN

        if cir.next != None:
            listN.next = cir

        # solve this problem

        get_pos = ListNode(-1)

        fast = tmp
        slow = tmp

        while(fast != None and slow !=None):
            # 无环的情况
            if(fast.next == None):
                get_pos.val = None
                return get_pos

            fast = fast.next.next
            slow = slow.next

            if(fast == slow):
                slow = tmp
                while(fast != slow):
                    slow = slow.next
                    fast = fast.next
                    get_pos.val += 1
                return get_pos
                break



head = [3,2,0,-4]
S = Solution()
print(S.hasCycle(head).val)


👇 Share | 分享 👇


要不赞赏一下?

微信
支付宝
PayPal
Bitcoin

版权声明 | Copyright

除非特别说明,本博客所有作品均采用知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议进行许可。转载请注明转自-
https://www.emperinter.info/2022/02/21/linked-list-cycle-ii/


要不聊聊?

我相信你准备留下的内容是经过思考的!【勾选防爬虫,未勾选无法留言】

*

*



微信公众号

👉 NewsLetter ❤️ 邮箱订阅 👈

优惠码


阿里云国际版20美元
Vultr10美元
搬瓦工 | Bandwagon应该有折扣吧?
域名 | namesiloemperinter(1美元)