from utils.listNode import ListNode

class Solution:
    def get_intersection(self, head1, head2):
        if not head1 or not head2:
            return None
        
        l1, l2 = self.get_length(head1), self.get_length(head2)
        node1, node2 = self.move_ahead(head1, l1 - l2), self.move_ahead(head2, l2 - l1)

        while node1 and node2:
            if node1 == node2:
                return node1
            
            node1 = node1.next
            node2 = node2.next
        
        return None
    
    def get_length(self, head):
        count = 0
        node = head
        while node:
            count += 1
            node = node.next
        
        return count
    
    def move_ahead(self, head, l):
        if l <= 0:
            return head
        
        curr = head
        while l > 0:
            curr = curr.next
            l -= 1
        
        return curr

class Solution2:
    def get_intersection(self, head1, head2):
        if not head1 or not head2:
            return None
        
        savedA, savedB = head1, head2

        while head1 != head2:
            head1 = savedB if not head1 else head1.next
            head2 = savedA if not head2 else head2.next
        
        return head1

one = ListNode(1)
two = ListNode(2)
three = ListNode(3)
four = ListNode(4)
five = ListNode(5)
six = ListNode(6)
seven = ListNode(7)

one.next = two
two.next = three
three.next = four
four.next = five
six.next = seven
seven.next = two

print(one)
print(six)

solution = Solution()
print(solution.get_intersection(one, six))
    
