<jupyter_start><jupyter_text>Q2.8 Loop DetectionGiven a circular linked list, return the node at the beginning of the loope.g. - A -> B -> C -> D -> E -> C- return CInput: Linked List headReturn: Node node<jupyter_code>from myLinkedLists import SinglyLinkedList, Node
""" 
Solution1:

Assume loop exist.
Traverse the list, store visited node in a hashset, if visited, return node

space O(n)
time O(n)

"""

def getLoopHead(head):
    visited = set()
    curr = head
    while curr not in visited:
        visited.add(curr)
        curr = curr.next
    return curr
"""
Solution2:

1. Two pointers, fast and slow, fast visits all even nodes, slow visits one by one, 
2. when fast meets slow
    - slow move one step a time
    - fast starts from head and move one step a time
3. the next time fast and slow meet is the beginning of the loop

space O(1)
time O(n)
"""

def getLoopHead2(head):
    if not head:
        return None
    
    fast = head
    slow = head
    
    # check if loop exist, update first, otherwise fast = slow = head -> break
    while fast.next:
        fast = fast.next.next
        slow = slow.next
        if fast == slow:
            break
    
    if not fast.next:
        # did not meet, no loop
        return None
    
    # next meeting point is the start of the loop
    fast = head
    while fast != slow:
        fast = fast.next
        slow = slow.next

    # return any of fast or slow
    return fast<jupyter_output><empty_output><jupyter_text>Prove of solution2:Assumption:1. k is the length from head to start of the loop2. M is the loop size1 -> 2 -> .. -> k -> k+1 -> ... -> k+M-1 -> kTry to find when will fast and slow meet:1. when slow moves k steps,    1. slow is at the start of loop    2. fast moves 2k steps    3. fast is at the k%M position in the loop2. Assume when slow moves k+x steps, fast and slow meet.    1. slow is at (x%M) in the loop    2. fast moves 2(k+x) steps => (k+2x)%M in the loop    3. fast and slow meet means they are at the same pos in the loop:           x%M = (k+2x)%M           => k+x = CM    4. This means if you move k+x from start of loop, it goes back to the beginning.Currently, slow has moved x steps in side the loop, therefore, if it moves k more steps, it reaches the start of the loop. (k+x = CM)If we let fast start from head of list and move k steps, it reaches the start of loop as well! (see Assumption1)Finally, if fast and slow both move k steps, they will meet at the start of the loop.Return any if they meet!  Testing<jupyter_code>def getRefs(head):
    refs = []
    while head:
        refs.append(str(id(head)))
        head = head.next
    return ' -> '.join(refs)

def getNode(head, idx):
    node = head
    for i in range(idx):
        if not node:
            return None
        node = node.next
    return node

def appendNode(head, idx):
    # given a linked list head and a idx, append node at idx to the end of the linked list
    node = getNode(head, idx)
    tail = head
    while tail.next:
        tail = tail.next
    tail.next = node
    return id(node)

def test(test_lists, func):
    total = len(test_lists)
    correct = 0
    
    for l, idx in test_lists:
        sll = SinglyLinkedList(l)
        print('sll: ', getRefs(sll.head), end='')
        
        nodeid = appendNode(sll.head, idx)
        
        print('->', nodeid)
        print('Loop Head: ', nodeid)
        
        node = func(sll.head)
        print('res: ', id(node))
        
        curr = id(node) == nodeid
        correct += curr
        print(curr, '\n', '-'*50, sep='')
    
    print(f'{correct}/{total}')
    if correct == total:
        print('All passed')
test_lists = [
    ([1,2,3,4,5], 2),
    ([1,2,3,4], 2),
    ([1,1,1,1,1,1], 2),
    ([2,4,6,4,2,1,3,52,100,24], 3),
    ([2,4,6,4,2,1,3,52,100], 3)
]
test(test_lists, getLoopHead2)<jupyter_output>sll:  140413814686664 -> 140413814689296 -> 140413814687560 -> 140413814686272 -> 140413814689520-> 140413814687560
Loop Head:  140413814687560
res:  140413814687560
True
--------------------------------------------------
sll:  140413814688176 -> 140413814689408 -> 140413814688568 -> 140413814687672-> 140413814688568
Loop Head:  140413814688568
res:  140413814688568
True
--------------------------------------------------
sll:  140413814686664 -> 140413814686328 -> 140413814686552 -> 140413815334728 -> 140413815333496 -> 140413815335400-> 140413814686552
Loop Head:  140413814686552
res:  140413814686552
True
--------------------------------------------------
sll:  140413814688176 -> 140413814689296 -> 140413815334784 -> 140413815334336 -> 140413815334616 -> 140413815334000 -> 140413815334504 -> 140413815336800 -> 140413815336856 -> 140413815336072-> 140413815334336
Loop Head:  140413815334336
res:  140413815334336
True
--------------------------------------------------
sll:  14041381468[...]
StarcoderdataJupyterStructuredCleanDedup