Intersection of Two Linked Lists easy

Problem Statement

Write a function to find the intersection of two singly linked lists. The lists intersect at a node if they share the same node object in memory. Your function should return the intersecting node. If the lists do not intersect, return null (or None in Python).

Example 1

Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3

Output: Intersecting node's reference: 8

Explanation: The intersected node's value is 8 (note that this must not be 0 if the two lists intersect). The intersecting node is a reference to the same node in both lists.

Example 2

Input: intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1

Output: Intersecting node's reference: 2

Steps

1. Calculate the lengths of both linked lists: Iterate through each list to determine their lengths.
2. Find the difference in lengths: Calculate the absolute difference between the lengths of the two lists.
3. Adjust pointers: Move the pointer of the longer list forward by the difference in lengths calculated in step 2. This aligns the pointers so that they are an equal distance from the intersection point (if it exists).
4. Iterate simultaneously: Move both pointers forward one node at a time. If the pointers ever point to the same node, that node is the intersection. If the pointers reach the end of their respective lists without finding a common node, there is no intersection.

Explanation

The core idea is to ensure both pointers are equidistant from the potential intersection point before starting the simultaneous traversal. By adjusting the longer list's pointer initially, we ensure that if an intersection exists, both pointers will reach it simultaneously. This avoids the need for complex bookkeeping or nested loops.

Code

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

def getIntersectionNode(headA, headB):
    """
    Finds the intersection node of two linked lists.

    Args:
        headA: The head node of the first linked list.
        headB: The head node of the second linked list.

    Returns:
        The intersecting node, or None if no intersection exists.
    """

    lenA = 0
    currA = headA
    while currA:
        lenA += 1
        currA = currA.next

    lenB = 0
    currB = headB
    while currB:
        lenB += 1
        currB = currB.next

    diff = abs(lenA - lenB)
    
    # Adjust pointers
    if lenA > lenB:
        currA = headA
        currB = headB
        for _ in range(diff):
            currA = currA.next
    else:
        currA = headA
        currB = headB
        for _ in range(diff):
            currB = currB.next

    # Iterate simultaneously
    while currA and currB:
        if currA == currB:
            return currA
        currA = currA.next
        currB = currB.next

    return None  # No intersection found

Complexity

• Time Complexity: O(m + n), where 'm' and 'n' are the lengths of the two linked lists. We traverse each list once.
• Space Complexity: O(1). The algorithm uses a constant amount of extra space. We only use a few pointers.