Technical Interview Question:

You are given two singly linked lists, list1 and list2. Write a function to find the intersection of the two lists, i.e., the node where the two lists intersect. If the two lists do not intersect, return null.

Here is the structure of a linked list node:

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

Create a function getIntersectionNode(list1, list2) that takes in the head nodes of the two linked lists as input and returns the intersection node if it exists, or null if the lists do not intersect.

Answer:

To find the intersection of two linked lists, one common approach is to use two pointers.

Approach:

1. Initialize two pointers p1 and p2 pointing to the heads of list1 and list2, respectively.
2. Traverse through list1 and list2 until p1 and p2 point to the same node, or both reach the end (i.e., become null).
3. If p1 becomes null, set it to the head of list2, and if p2 becomes null, set it to the head of list1.
   • This step is essential because the lengths of list1 and list2 may be different. By moving the pointer pointing to the shorter list to the head of the other list, we can ensure both pointers traverse the same total length.
4. Repeat step 2 until p1 and p2 point to the same node, or both reach the end.
5. Return the node at which p1 and p2 meet, or null if they reach the end without intersecting.

Pseudocode:

def getIntersectionNode(list1, list2):
    if list1 is None or list2 is None:
        return None

    p1, p2 = list1, list2

    while p1 != p2:
        p1 = p1.next if p1 else list2
        p2 = p2.next if p2 else list1

    return p1

The time complexity of this approach is O(m + n), where m and n are the lengths of list1 and list2, respectively. This is because we traverse each list once. The space complexity is O(1) as we only use two pointers.