Find the Intersection of Two Linked Chains

Problem Statement

Given the heads of two acyclic singly linked lists, headA and headB, return the node at which the two lists intersect. If the two linked lists have no intersection at all, return null.

For example, the following two linked lists begin to intersect at node c1:

• List A: a1 -> a2 -> c1 -> c2 -> c3
• List B: b1 -> b2 -> b3 -> c1 -> c2 -> c3

Requirements

• You must solve the problem in O(n + m) time, where n and m are the lengths of the two lists.
• You must use O(1) extra space (i.e., you cannot use a hash set to store visited nodes).
• Your solution must not modify the original structure of the linked lists.

Function Signature

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

def getIntersectionNode(headA: ListNode, headB: ListNode) -> ListNode:
    pass

Examples

Example 1:

• Input: headA = [4,1,8,4,5], headB = [5,6,1,8,4,5]
• Output: Node(8)
• Explanation: The lists intersect at node with value 8.

Example 2:

• Input: headA = [2,6,4], headB = [1,5]
• Output: null
• Explanation: No intersection.

Edge Cases

• One or both lists are empty.
• The lists intersect at the very last node.
• The lists are of significantly different lengths.