Intersection of Two Linked Lists

Given the heads of two 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:

The test cases are generated such that there are no cycles anywhere in the entire linked structure. Note that the linked lists must retain their original structure after the function returns.

Example 1: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3 Output: Intersected at '8'

Example 2: intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1 Output: Intersected at '2'

Example 3: intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2 Output: No intersection

Explain a solution that runs in O(m + n) time and use only O(1) memory. Provide a code example with the time and space complexity.

## Find Intersection of Two Linked Lists

This problem requires finding the intersection node of two singly linked lists. If there is no intersection, return `null`. The key constraint is to achieve this in O(m + n) time and O(1) space complexity.

### 1. Brute Force Solution

A simple brute-force approach would be to compare each node of the first list with every node of the second list. This is highly inefficient but helps to understand the problem.

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

2. Optimal Solution (Two Pointers)

The optimal solution involves using two pointers. The main idea is to traverse both lists, and when one pointer reaches the end of its list, it switches to the head of the other list. This ensures that both pointers travel the same combined distance, and if the lists intersect, the pointers will eventually meet at the intersection node.

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

def get_intersection_node(headA, headB):
    if not headA or not headB:
        return None

    pointer_a = headA
    pointer_b = headB

    while pointer_a is not pointer_b:
        # If pointer_a reaches the end, move it to headB
        pointer_a = headA if pointer_a is None else pointer_a.next
        # If pointer_b reaches the end, move it to headA
        pointer_b = headB if pointer_b is None else pointer_b.next

    return pointer_a  # or pointer_b, since they are the same at the intersection

3. Big(O) Run-Time Analysis

The time complexity of the optimal solution is O(m + n), where m and n are the lengths of the two linked lists.

• Each pointer traverses both lists at most once.
• In the worst case, each pointer travels the combined length of both lists.

4. Big(O) Space Usage Analysis

The space complexity of the optimal solution is O(1), as it only uses two pointers, regardless of the size of the linked lists. No additional data structures are used.

5. Edge Cases

• One or both lists are empty: The function should return None.
• No intersection: The pointers will both reach None at the same time, and the function returns None.
• Intersection at the head: The pointers will meet at the head node.
• Lists are identical: The pointers will meet at the head node.

Code Explanation

1. Initialization: Two pointers, pointer_a and pointer_b, are initialized to the heads of headA and headB, respectively.
2. Traversal: The while loop continues until pointer_a and pointer_b are the same node (i.e., the intersection is found) or both are None (i.e., no intersection).
3. Pointer Switching:
   • If pointer_a reaches the end of headA (i.e., pointer_a is None), it is moved to the head of headB.
   • Similarly, if pointer_b reaches the end of headB, it is moved to the head of headA.
4. Return Value: If the loop exits because pointer_a and pointer_b are the same, that node is the intersection node. If the loop exits because both pointers are None, there is no intersection, and None is returned.

Illustration

Let's illustrate with an example:

listA: 4 -> 1 -> 8 -> 4 -> 5
listB: 5 -> 6 -> 1 -> 8 -> 4 -> 5

1. pointer_a starts at 4, pointer_b starts at 5.
2. They traverse their respective lists until pointer_a reaches the end of listA and moves to the head of listB. Similarly, pointer_b reaches the end of listB and moves to the head of listA.
3. Eventually, both pointers will reach the node with value 8 at the same time, indicating the intersection.