Finding the Intersection Point of Two Linked Lists

Introduction

The task is to find the intersection point of two given linked lists, i.e., the first common node where the two lists converge.
If the two linked lists do not intersect, return null.

Problem Explanation

Given: Two linked lists (head1 and head2)
Objective: Find the first common node between the two linked lists.
Example: Given Linked List 1: 1 -> 2 -> 4 -> 6 -> 7 and Linked List 2: 3 -> 5 -> 6 -> 7, the intersection is at node with value 6.

Extreme Naive Solution

Traverse First Linked List and Store Nodes in Memory: (1 -> 2 -> 4 -> 6 -> 7) Using Hashing
- Use a map data structure to store each node in the first linked list.
Traverse Second Linked List: (3 -> 5 -> 6 -> 7)
- For each node, check if the node exists in the map.
- If found, that is the intersection point.
- If not found and you reach null, return null.

Pseudo Code

- Take a map data structure storing node and integer
- Traverse first linked list (temp1 at head1), store nodes in map
- Traverse second linked list (temp2 at head2)
  - If node found in map, return temp2
  - Else traverse next node
- If entire traversal completed, return null

Time and Space Complexity

Time Complexity: O(N1 + N2)
Space Complexity: O(N1) or O(N2)

Optimized Solution 1: Align Levels

Compute Lengths: Compute lengths of both linked lists.
Align Their Levels: Adjust the starting point of the longer list so both lists are at the same level for comparison.
Traverse and Compare: Move both pointers one step at a time until they collide or until both reach null.

Pseudo Code

- Compute lengths of both linked lists (N1, N2)
- Find the difference (D)
- Advance the longer list by D steps
- Move both pointers one step at a time until intersection point found

function findIntersection(head1, head2, D):
  while D: 
    longerList = longerList.next
    D--
  while head1 != head2:
    head1, head2 = head1.next, head2.next
  return head1

if N1 > N2:
  return findIntersection(head1, head2, N1 - N2)
else:
  return findIntersection(head2, head1, N2 - N1)

Optimized Solution 2: Two-pointer Approach

Initialize Two Pointers: One starting at head1 and the other at head2.
Simultaneous Traversal: Move each pointer one step at a time. When a pointer reaches the end, redirect it to the head of the other list.
Collision at Intersection: When the pointers collide, that is the intersection point.

Pseudo Code and Implementation

- Initialize two pointers temp1 and temp2 at head1 and head2
- Traverse both lists simultaneously
- If any pointer reaches null, redirect to the head of the other list
- If pointers collide, return that node

function getIntersectionNode(headA, headB):
  if headA == null or headB == null: return null
  temp1, temp2 = headA, headB
  while temp1 != temp2:
    temp1 = headB if temp1 == null else temp1.next
    temp2 = headA if temp2 == null else temp2.next
  return temp1

Proof of Algorithm

Aligned steps ensure that both traversals match up by length difference, checking all nodes for collisions.
If lengths are equal, they will collide or both reach null simultaneously.
Time Complexity: O(N1 + N2)
Space Complexity: O(1)

Important Edge Cases

Empty Lists: If either list is empty, return null.
Same Head (Direct Intersection): Directly compare heads for first intersection point.
No Intersection: Both pointers would eventually simultaneously become null.

Conclusion

Understanding brute force and optimized approaches is crucial.
Two-pointer approach is efficient both in terms of time and space.
Useful in technical interviews for demonstrating problem-solving and optimization techniques.

Note: Full implementation in C++, Java, Python, and JavaScript can be found in the description links. Make sure to subscribe for more algorithm discussions!