leetcode142-- Linked List Cycle II (判断链表是否有环,并找出环的入口位置)

leetcode142-- Linked List Cycle II (判断链表是否有环,并找出环的入口位置)

题目

刚才是判断有没有环,现在是确定环的位置,如果没有环的话就返回None,有的话就找出环的位置,想法是再用两个指针,一个是从head出发,一个是从之前walker和runner相见的地方出发,当这两个指针相见的时候就是环的入口处.


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

class Solution(object):
    def detectCycle(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        
        # get cross
        
        walker = head
        runner = head
        
        while runner != None and runner.next != None:
            runner = runner.next.next
            walker = walker.next
            
            if runner==walker:
                break
                
        # 只要不是因为break而导致的就返回None
        if runner == None or runner.next == None:
            return None
        
        first = head
        second = walker
        
        while first != second:
            first = first.next
            second = second.next
        
        return first
                
        
        

打赏,谢谢~~

取消

感谢您的支持,我会继续努力的!

扫码支持
扫码打赏,多谢支持~

打开微信扫一扫,即可进行扫码打赏哦