LC interview question 02.07 Linked list intersection & lc142 Circular linked list II

Interview questions 02.07. The list intersects

thought ： Find the linked list A length , Linked list B length , Get AB The difference in length . If A Long , So let's A Go ahead , Go to the AB Length difference , Finally, we will meet at the intersection .

notes ： picture source - Random code recording

Code ：

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

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        def action(lengthA, lengthB, nodeA, nodeB):
            length = lengthA - lengthB
            for i in range(length):
                nodeA = nodeA.next
            print("nodeA.val",nodeA.val)
            while nodeA and nodeB:
                if nodeA == nodeB:
                    print(nodeA.val)
                    return nodeA                  
                nodeA = nodeA.next
                nodeB = nodeB.next
   
            return None    
    
        if not headA or not headB:
            return None
        lengthA, lengthB = 0, 0
        nodeA, nodeB = headA, headB
        while nodeA:
            nodeA = nodeA.next
            lengthA += 1

        while nodeB:
            nodeB = nodeB.next
            lengthB += 1
        print("lengthA", lengthA)
        print("lengthB", lengthB)
        nodeA, nodeB = headA, headB
        if lengthA > lengthB:
            return action(lengthA, lengthB, nodeA, nodeB)
        else:
            return action(lengthB, lengthA, nodeB, nodeA)

LC142. Circular list II

Q1： Judge whether there is a ring

Q2： Judge the position of the ring inlet ？

notes ： picture source - Random code recording
Set up ：fast Two steps at a time ,slow One step at a time . If there is a ring ,fast It must be better than slow Enter the ring first , Finally, it must meet in the ring .

When we met ,fast The journey x+y+n(y+z) ,slow The journey x+y,fast Speed is slow Of 2 times

Then we can get the formula ：x+y+n(y+z) = 2(x+y)

Simplify to get ：x = (n-1)(y+z)+z What does that mean ？ Two nodes ab Same speed , A node a Start from the beginning , Another node b Start from where you meet , Eventually, they will meet at the ring entry node . It's just b Maybe it's in the ring 0 Circle or (n-1) Circle problem .

The code is as follows ：

class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        fast, slow = head, head
        cur = head
        #  If it is empty , Then there is no ring 
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next

            # fast==slow, here fast and slow Both point to the encounter node 
            if fast == slow:
                while slow != cur:
                    slow = slow.next
                    cur = cur.next
                return cur
                # cur == slow, Meet at the ring entrance ,index It is the index of the ring entry 
        
        return None
        

Q3： What to ask fast and slow When we met ,slow It must be gone x+y, instead of x+y+n(y+z)

First slow When entering the ring ,fast It must have entered the ring . If slow Ring entry ,fast Also at the ring entrance , Then expand the ring into a straight line , It must be at the ring entrance 3 Meeting place .

But the actual ：slow When entering the ring ,fast It must be somewhere in the ring , As shown in the figure below . Then it means in fast Go to the ring entrance 3 When , go k+n,slow go (k+n)/2<n, It means that slow Did not go to the ring mouth 3, So they are in Huankou 2- Ring mouth 3 On the way to meet , That is to say slow The link in Kaishi has been connected with fast Met .

Then a classmate said again , Why? fast Can't skip ？ I have just said it once ,fast be relative to slow Is to move one node at a time , So it's impossible to jump over .

Reference link

[1] Random code recording https://programmercarl.com/%E9%9D%A2%E8%AF%95%E9%A2%9802.07.%E9%93%BE%E8%A1%A8%E7%9B%B8%E4%BA%A4.html#%E6%80%9D%E8%B7%AF