AlgoDesign

Overlapping lists cycles

1class Solution:
2    def overlappingListsCycles(self, headA, headB):
3        cycleA, cycleB = self.startOfCycle(headA), self.startOfCycle(headB)
4
5        if not cycleA and not cycleB: return self.overlappingLists(headA, headB)
6        elif (not cycleA and cycleB) or (not cycleB and cycleA): return None
7
8        tmp = cycleA.next
9        while tmp and tmp != cycleB: tmp = tmp.next
10
11        return tmp if tmp == cycleB else None
12    
13    def overlappingLists(self, headA, headB):
14        first, second = headA, headB
15
16        while first and second and first != second:
17            first = headB if not first else first.next
18            second = headA if not second else second.next
19        
20        return first
21
22    def startOfCycle(self, node):
23        fast, slow = node, node
24        while fast and fast.next:
25            slow = slow.next
26            fast = fast.next.next
27            if slow == fast: break
28        
29        if slow: length = self.cycleLength(slow)
30        else: return None
31
32        first, second = slow, node
33        for _ in range(length):
34            first = first.next
35            second = second.next
36        
37        return first
38
39    def cycleLength(self, node):
40        res, n = 1, node.next
41        while n != node:
42            res += 1
43            n = n.next
44
45        return res