How would you find the intersection point of two linked lists?

Finding the intersection point of two linked lists is a common problem in computer programming interviews. The problem can be solved efficiently using two pointers.

Firstly, let’s define the problem: given two linked lists, we need to find the point at which they intersect, or return ‘null‘ if they do not.

## 1. Brute Force Solution:

The simplest way, though not the most efficient, is to use two nested loops. The outer loop is used for each node of the first linked list and the inner loop compares it with every node of the second linked list. The time complexity for this solution is **O(m*n)**.

## 2. Hash Table/Map Solution:

By using a hash table or a map, we can store the nodes of one linked list and then check each node of the other linked list to see if it’s in the hash table/map or not. However, this method has additional space complexity and takes **O(m + n)** time complexity.

## 3. Two Pointers Technique Solution:

To solve the problem in an efficient manner (without using additional memory), we would employ a strategy involving two pointers:

(i) Traverse the two linked lists to get their lengths - say ‘m‘ and ‘n‘ for list 1 and list 2 respectively.

(ii) Calculate the difference in lengths ‘d = |m - n|‘.

(iii) Move the pointer of the larger list ‘d‘ nodes ahead.

(iv) Now traverse both lists simultaneously. When the pointers to the two lists are equal, we have found the intersection.

Here’s a Python code snippet showing how to implement it:

def getIntersectionNode(headA, headB):
    lenA, lenB = 0, 0
    tempHeadA, tempHeadB = headA, headB
    
    while tempHeadA is not None:
        tempHeadA = tempHeadA.next
        lenA += 1

    while tempHeadB is not None:
        tempHeadB = tempHeadB.next
        lenB += 1

    tempHeadA, tempHeadB = headA, headB

    if lenA > lenB:
        for _ in range(lenA - lenB):
            tempHeadA = tempHeadA.next
    else:
        for _ in range(lenB - lenA):
            tempHeadB = tempHeadB.next

    while tempHeadA != tempHeadB:
        tempHeadA = tempHeadA.next
        tempHeadB = tempHeadB.next

    return tempHeadA

This algorithm is O(m + n), m and n being the lengths of the two linked lists. This is because we’re essentially doing a linear scan of both linked lists to find the lengths and then another linear scan to find the intersection.

The space complexity is O(1), or constant, because we’re only using a fixed amount of space to store the pointers and length variables, regardless of the size of the input linked lists.

That’s all about finding the intersection point of two linked lists. Note that this problem and its solutions are a good example of how trade-off between time and space complexities can be managed in different situations.