Intersection of Two Linked Lists

Table Of Contents

show

Problem Statement
Approach 1: Brute Force

C++ Code
Java Code
Python Code

Approach 2: Hashing

C++ Implementation
Java Implementation
Python Implementation

Approach 3: Two Pointers

C++ Code For Two Pointers Approach
Java Code For Two Pointers Approach
Python Code For Two Pointers Approach

Practice Question
Additional Resources

Problem Statement

Given the heads of two linked lists A and B. The task is to return the node where both the linked lists intersect. If there is no point of intersection, return NULL.

Examples:
Input:

Output: Node 8
Explanation: Shown in image

Confused about your next job?

In 4 simple steps you can find your personalised career roadmap in Software development for FREE

Expand in New Tab

Approach 1: Brute Force

A simple approach is to, traverse every node of the linked list B, for each node of A and simply check if any of the nodes is present in the list B.

C++ Code

ListNode * getIntersectionNode(ListNode * headA, ListNode * headB) {
  while (headA != nullptr) {
    ListNode * pB = headB;
    while (pB != nullptr) {
      if (headA == pB) return headA;
      pB = pB -&gt; next;
    }
    headA = headA -&gt; next;
  }
  return nullptr;
}

Java Code

 public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
  while (headA != null) {
    ListNode pB = headB;
    while (pB != null) {
      if (headA == pB) return headA;
      pB = pB.next;
    }
    headA = headA.next;
  }
  return null;
}

Python Code

def getIntersectionNode(self, headA: ListNode, headB: ListNode) -&gt; ListNode:
    while headA is not None:
        pB = headB
        while pB is not None:
            if headA == pB:
                return headA
            pB = pB.next
        headA = headA.next
 
    return None

Time Complexity:O(N * M), where N and M is the size of the linked lists
Space Complexity:O(1), as no extra space is used.

Approach 2: Hashing

In the previous approach, instead of traversing through all the nodes of B, we can simply keep track of a hashmap that stores each node of B. Now simply traverse list A, and check if any of the nodes is already present in the hashmap. If true, then it is the intersection point.

Algorithm

Initialise a hashmap of nodes.
Traverse the list B and store each node address into the hashmap.
Traverse the array A and if the current node is already present in the hashmap, then it is the intersection point, else continue traversing.
If list A is exhausted, there is no intersection point. Hence, return NULL.

C++ Implementation

ListNode * getIntersectionNode(ListNode * headA, ListNode * headB) {
  set &lt; ListNode * &gt; nodes_in_B;
 
  while (headB != nullptr) {
    nodes_in_B.insert(headB);
    headB = headB -&gt; next;
  }
 
  while (headA != nullptr) {
    if (nodes_in_B.find(headA) != nodes_in_B.end()) {
      return headA;
    }
    headA = headA -&gt; next;
  }
 
  return nullptr;
}

Java Implementation

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
   Set &lt; ListNode > nodesInB = new HashSet &lt; ListNode > ();
 
   while (headB != null) {
     nodesInB.add(headB);
     headB = headB.next;
   }
 
   while (headA != null) {
     if (nodesInB.contains(headA)) {
       return headA;
     }
     headA = headA.next;
   }
 
   return null;
 }

Python Implementation

def getIntersectionNode(self, headA: ListNode, headB: ListNode) -&gt; ListNode:
    nodes_in_B = set()
 
    while headB is not None:
        nodes_in_B.add(headB)
        headB = headB.next
 
    while headA is not None:
        if headA in nodes_in_B:
            return headA
        headA = headA.next
 
    return None

Time Complexity:O(N + M), where N and M is the size of the linked list
Space Complexity:O(M), since the nodes of list B are stored.

Approach 3: Two Pointers

While we have already achieved the best time complexity possible, but is it possible to reduce the space complexity?

Well, it can be done in O(1) using a two-pointer approach. Let’s understand how.

The key idea to note is that, if the two linked lists contain a common point, the length from that intersection point to the tail will be the same.

Since the tail length must be the same, the intersection node should be any of the first five nodes in the given image.

Therefore, place two-pointers and keep checking if the nodes are equal.

Algorithm

Set a pointer p1 to list A.
Set a pointer p2 to list B.
Run a while loop and while the nodes pointed by p1 and p2 are not same:
- If p1 is pointing to NULL, set p1 to head of B.
- Else, move to the next node of A.
- If p2 is pointing to NULL, set p2 to head of A.
- Else, move to the next node of B.
Return the node pointed by p1.

C++ Code For Two Pointers Approach

ListNode * getIntersectionNode(ListNode * headA, ListNode * headB) {
  ListNode * pA = headA;
  ListNode * pB = headB;
  while (pA != pB) {
    pA = pA == nullptr ? headB : pA -&gt; next;
    pB = pB == nullptr ? headA : pB -&gt; next;
  }
  return pA;
}

Java Code For Two Pointers Approach

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
  ListNode pA = headA;
  ListNode pB = headB;
  while (pA != pB) {
    pA = pA == null ? headB : pA.next;
    pB = pB == null ? headA : pB.next;
  }
  return pA;
}

Python Code For Two Pointers Approach

def getIntersectionNode(self, headA: ListNode, headB: ListNode) -&gt; ListNode:
    pA = headA
    pB = headB
 
    while pA != pB:
        pA = headB if pA is None else pA.next
        pB = headA if pB is None else pB.next
 
    return pA

Time Complexity:O(N + M), where N and M is the size of the linked list
Space Complexity:O(1), since no extra space is used.

Practice Question

Intersection Of Linked Lists