Intersection of Two Linked Lists Interview Question for Meta

Given two singly linked lists, write a function to find the node at which the two lists intersect. If the lists do not intersect, return null. Two linked lists intersect if they share the exact same node, not just nodes with equal values. You can assume there are no cycles within either linked list.

For example:

List A: 3 -> 7 -> 8 -> 10 List B: 99 -> 1 -> 8 -> 10 Intersection: Node with value 8
List A: 2 -> 6 -> 4 List B: 1 -> 5 Intersection: null
List A: 1 -> 9 -> 1 -> 2 -> 4 List B: 3 -> 2 -> 4 Intersection: Node with value 2
List A: 4 -> 1 -> 8 -> 4 -> 5 List B: 5 -> 6 -> 1 -> 8 -> 4 -> 5 Intersection: Node with value 8

Your function should have the following signature:

python def getIntersectionNode(headA, headB): # write your code here pass

Intersection of Two Linked Lists

Here's how to find the intersection node of two linked lists. I'll start with a brute-force approach and then move on to a more efficient solution.

1. Naive (Brute-Force) Solution

The most straightforward approach is to iterate through each node of the first linked list and, for each node, iterate through the second linked list to see if we find a matching node (same memory address). If we find a match, that's our intersection node.

Big(O) Runtime:

O(m*n), where 'm' is the length of the first linked list and 'n' is the length of the second linked list. This is because, in the worst case, we compare every node in the first list to every node in the second list.

Big(O) Space Usage:

O(1). We're not using any extra space; we're just comparing nodes.

Code (Python):

python def get_intersection_node_brute_force(headA, headB): current_a = headA while current_a: current_b = headB while current_b: if current_a == current_b: return current_a current_b = current_b.next current_a = current_a.next return None

2. Optimal Solution

A more efficient solution involves these steps:

Find the lengths of both linked lists. Iterate through each list and count the number of nodes.
Determine the difference in lengths. This will tell us how much further ahead one list is than the other.
Move the pointer of the longer list ahead by the difference. This aligns the starting points of the two lists.
Iterate through both lists simultaneously. Compare the nodes at each step. If we find a matching node, that's the intersection.
If we reach the end of both lists without finding a match, there's no intersection.

Big(O) Runtime:

O(m + n), where 'm' and 'n' are the lengths of the two linked lists. We iterate through each list at most once (or twice, depending on how you count finding the lengths).

Big(O) Space Usage:

O(1). We're only using a few extra variables to store lengths and pointers; the space used doesn't scale with the input size.

Code (Python):

python def get_intersection_node(headA, headB): lenA = 0 lenB = 0 currA = headA currB = headB

# Find lengths of the lists
while currA:
    lenA += 1
    currA = currA.next

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

currA = headA
currB = headB

# Move the pointer of the longer list forward
if lenA > lenB:
    for _ in range(lenA - lenB):
        currA = currA.next
elif lenB > lenA:
    for _ in range(lenB - lenA):
        currB = currB.next

# Traverse both lists until intersection is found
while currA and currB:
    if currA == currB:
        return currA
    currA = currA.next
    currB = currB.next

return None

3. Edge Cases

Empty Lists: If either list is empty, there's no intersection (return None).
No Intersection: If the lists don't intersect at all, the loop will finish, and we'll return None.
Lists are the same: If the lists are exactly the same (same nodes, same order), the function will work correctly and return the head of the list.
Circular Linked Lists (advanced): If the lists have cycles, this method might not work correctly (it might loop forever). Dealing with cycles requires more advanced cycle detection techniques (e.g., Floyd's cycle-finding algorithm).

4. Explanation

The optimal solution works by aligning the two lists such that if they intersect, they will do so at the same distance from their respective current pointers. By first finding the lengths and then advancing the pointer of the longer list, we ensure that when we iterate through them simultaneously, we'll hit the intersection point at the same time (if one exists).