The Intersection Point of Two Linked Lists

The Intersection Point of Two Linked Lists
The Intersection Point of Two Linked Lists

Introduction 

Linked lists are one of the frequently asked data structures in interviews. Some of the questions on the linked list asked in product-based companies like Amazon, Microsoft are  Detect And Remove Cycle, Merge two sorted linked lists, etc. 

This blog will discuss the interview problem: the intersection point of two linked lists previously asked in companies like Amazon, Adobe, Microsoft, Visa, etc. This blog requires a thorough understanding of Linked List so, please go through the blog A Brief Introduction To Linked Lists for a better understanding.

Problem Statement

Given two linked lists, write a program to find the intersection point of two linked lists. Return the node data at which merging starts and if there is no merging, return -1.


For example:-

Input:

Linked List A: 4 -> 1 -> 8 -> 4 -> 5

Linked List B: 5 -> 6 -> 1 -> 8 -> 4 -> 5

Output:

8

Explanation:

The linked lists intersect at the node with a value of 8.

Recommended: Please try to solve the intersection point of two linked lists on “CODESTUDIO” first before moving on to the solution. 

Now let’s see various approaches to find the intersection point of two linked lists.

Driver code

Let’s check out the main function before moving to each approach. We initialize two linked lists in the main function: list1 and list2 with the common nodes. The value of the intersection node is obtained from the function intersectionPoint(). 

Main function:

public class Main {
  public static void main(String[] args) {
    // linked list 1
    ListNode list1 = new ListNode(4);
    list1.next = new ListNode(1);
    list1.next.next = new ListNode(8);
    list1.next.next.next = new ListNode(4);
    list1.next.next.next.next = new ListNode(5);
    System.out.print("First Linked List is ");
    printList(list1);
 
    // linked list 2
    ListNode list2 = new ListNode(5);
    list2.next = new ListNode(6);
    list2.next.next = new ListNode(1);
    list2.next.next.next = list1.next.next;
    System.out.print("Second Linked List is ");
    printList(list2);
 
    int result = intersectionPoint(list1, list2);
    System.out.println("The intersection point of two linked lists: " + result);
  }
}

Let’s also check out the ListNode class and printList() function, repeatedly used in the program.

Class ListNode:

// class representing the node in the linked list
class ListNode {
  int val;
  ListNode next;
 
  ListNode(int val) {
    this.val = val;
  }
}

Function printList():

// function to print linked list
private static void printList(ListNode head) {
    while (head != null) {
      System.out.print(head.val + " ");
      head = head.next;
    }
    System.out.println();
}

The intersection point of two linked lists: Using Loops

In this approach, nested loops are used. The outer loop selects a node from the first linked list, and the inner loop selects a node from the second linked list. When both the linked lists reach the same node, return the value of the node.

Steps:

  1. Initialize an outer loop for the first linked list.
  2. Initialize the inner loop for the second linked list.
  3. Traverse the linked lists till the intersecting node is met.
  4. Return the value of the intersecting node.

Code:

public class Main {
  // function to find the intersection of two linked lists
  private static int intersectionPoint(ListNode list1, ListNode list2) {
ListNode firstTemp = list1;
    while (firstTemp  != null) {
      ListNode temp = list2;
      while (temp != null) {
        // if both linked lists points to the same node
        if (firstTemp  == temp) {
          return firstTemp .val;
        }
        temp = temp.next;
      }
      firstTemp = firstTemp .next;
    }
   // if there is no intersecting node
    return -1;
  }
}

Output

First Linked List is 4 1 8 4 5
Second Linked List is 5 6 1 8 4 5
The intersection point of two linked lists is: 8

Complexity Analysis: 

  • Time Complexity: O(m * n) as there is a nested loop.
  • Space Complexity: O(1)  

 m: number of nodes in the first linked list

 n: number of nodes in the second linked list

The intersection point of two linked lists: Using Hashing

In this approach, the nodes of the first linked list are stored in a HashSet. Then the nodes in the second linked list are stored in the HashSet till the intersecting point of two Linked Lists is met. 

Steps:

  1. Create an empty HashSet.
  2. Traverse the first linked list and store all the nodes.
  3. Traverse the second linked list and store the nodes till the intersecting node is met.
  4. Return the value of the intersecting node.

Code:

import java.util.HashSet;
 
public class Main {
  // function to find the intersection of two linked lists
  private static int intersectionPoint(ListNode list1, ListNode list2) {
        // define hashset
       HashSet<ListNode> hashset = new HashSet<ListNode>();
      
       // add all the nodes in the hashset
  ListNode firstTemp = list1;
       while(firstTemp  != null) {
         hashset.add(firstTemp );
         firstTemp = firstTemp .next;
       }
      
       // check if the intersecting node is present
  ListNode secondTemp = list2;
       while(secondTemp != null) {
         if(hashset.contains(secondTemp ))
           return secondTemp.val;
         hashset.add(secondTemp );
         list2 = secondTemp.next;
       }
      
       // if there is no intersecting node
    return -1;
  }
}

Output

First Linked List is 4 1 8 4 5
Second Linked List is 5 6 1 8 4 5
The intersection point of two linked lists is: 8

Complexity Analysis: 

  • Time Complexity: O(m + n) as the linked lists are traversed once.
  • Space Complexity: O(m + n)  as extra space is required for the HashSet.

The intersection point of two linked lists: Using the difference of node counts

In this approach, the bigger node is traversed until both the linked lists have the same size. Then both the linked lists are traversed at the same speed till the intersection point is encountered.

Steps:

  1. Find the size of linked lists.
  2. Calculate the difference (d) in the sizes of the linked list.
  3. Swap the linked list to make the first linked list larger (if required).
  4. Traverse the bigger list till d.
  5. Both the linked lists have equal nodes from the intersection point, and then traverse until the intersection point is reached.

Code:

public class Main {
 // function to get the size of the linked lists
  private static int getSize(ListNode list) {
    int size = 0;
    while (list != null) {
      size++;
      list = list.next;
    }
    return size;
  }
// function to find the intersection of two linked lists
 private static int intersectionPoint(ListNode list1, ListNode list2) {
   int size1 = getSize(list1), size2 = getSize(list2);
   int sizeDifference = Math.abs(size1 - size2);
 
   ListNode tempList1 = list1, tempList2 = list2;
   // swap to make the first linked list larger in size
   if (size2 > size1) {
     ListNode temp = tempList2;
     tempList2 = tempList1;
     tempList1 = temp;
   }
 
   // traverse the bigger linked lists till both the linked lists have same number
   // of nodes
   for (int i = 0; i < sizeDifference; i++) {
     tempList1 = tempList1.next;
   }
 
   // check if the linked lists have a common node
   while (tempList1 != null && tempList2 != null) {
     if (tempList1 == tempList2) {
       return tempList1.val;
     }
     tempList1 = tempList1.next;
     tempList2 = tempList2.next;
   }
 
   // if there is no intersecting node
   return -1;
 }
}

Output

First Linked List is 4 1 8 4 5
Second Linked List is 5 6 1 8 4 5
The intersection point of two linked lists is: 8

Complexity Analysis: 

  • Time Complexity: O(m + n) 
  • Space Complexity: O(1)  

The intersection point of two linked lists: Using Floyd’s Cycle Detection Algorithm

In this approach, the first linked list is converted to a circular linked list by connecting the tail to its head. Then two pointers are considered: one pointing to the head node and the other pointing to the kth (total number of nodes in the loop) node from the head. These pointers are then moved with the same speeds to get the intersection point of two linked lists.

Refer to the blog Floyd’s Cycle Detection Algorithm for a better understanding.

Steps:

  1. Convert the first linked list into a circular linked list.
  2. Detect if a cycle is present.
  3. Set two pointers: one at the head of the loop and the other at the kth node.
  4. Simultaneously move the list and current pointers at the same speed until they meet.
  5. Return the current value, which is the value of the intersecting node.
  6. Remove the cycle from the linked list.

Code:

public class Main {
  // function to find node
  private static ListNode findNode(ListNode slow, ListNode list) {
    // count of nodes in the loop
    int count = 1;
    for (ListNode pointer = slow; pointer.next != slow; pointer = pointer.next) {
      count++;
    }
 
    // pointer at a distance of count from the start of the loop
    ListNode current = list;
    for (int i = 0; i < count; i++) {
      current = current.next;
    }
 
    // simultaneously move the list and current pointers at the same speed until they meet
    while (current != list) {
      current = current.next;
      list = list.next;
    }
 
    // returns the starting node of the loop
    return current;
  }
 
  // function to detect the cycle
  private static ListNode identifyCycle(ListNode list) {
    ListNode slow = list, fast = list;
    while (fast != null && fast.next != null) {
      // move slow by one pointer
      slow = slow.next;
 
      // move fast by two pointers
      fast = fast.next.next;
 
      // if pointers meet at any node, the linked list contains a cycle
      if (slow == fast) {
        return slow;
      }
    }
 
    // cycle is not present in the linked list
    return null;
  }
 
  // function to find the intersection of two linked lists
  private static int intersectionPoint(ListNode list1, ListNode list2) {
    ListNode previous = null, current = list1;
 
    // traverse the list1 and get the pointer to the last nod
    while (current != null) {
      previous = current;
      current = current.next;
    }
 
    // create a cycle in the list1
    if (previous != null) {
      previous.next = list1;
    }
 
    // pointer to the loop node
    ListNode slow = identifyCycle(list2);
 
    // find the intersection node
    ListNode intersectionNode = null;
    if (slow != null) {
      intersectionNode = findNode(slow, list2);
    }
 
    // remove cycle in the list1
    if (previous != null) {
      previous.next = null;
    }
 
    int result = intersectionNode == null ? -1 : intersectionNode.val;
    return result;
  }
}

Output

First Linked List is 4 1 8 4 5
Second Linked List is 5 6 1 8 4 5
The intersection point of two linked lists is: 8

Complexity Analysis: 

  • Time Complexity: O(m + n) 
  • Space Complexity: O(1)  

The intersection point of two linked lists: Two-pointer Approach

In this approach, two pointers pointing at the head node of the linked list are taken. When the pointer reaches the end of the linked list, it is reassigned to the other list. After both the pointers are reassigned, they will be equidistant from the intersection point. Finally, the intersection point of two linked lists is obtained when the pointers become equal and are not null.

Steps:

  1. Initialize two pointers head1 and head2, at the head of list1 and list2, respectively.
  2. Traverse through the linked lists
  3. When head1 reaches the end of a list, then assign it to list2.
  4. When head2 reaches the end of a list, then assign it to list1.
  5. When both of them are reassigned, they will be equidistant from the intersection point.
  6. The point where head1 equals head2 and both are not null is the intersection point of two linked lists.

Code:

public class Main {
  // function to find the intersection of two linked lists
  private static int intersectionPoint(ListNode list1, ListNode list2) {
      ListNode head1 = list1;
      ListNode head2 = list2;
  
      // no intersection point if any one of the head is null
      if (head1 == null || head2 == null) {
          return -1;
      }
  
      // traverse through the linked lists until intersection node is reached
      while (head1 != head2) {
          head1 = head1.next;
          head2 = head2.next;
         
          // intersection point if both the nodes are same and are not null
          if (head1 == head2) {
            // no intersection node
            if(head1 == null)
              return -1;
            else
              return head1.val;
          }
  
          // reassign it to the list2 when head1 reaches the end
          if (head1 == null) {
              head1 = list2;
          }
         
          // redirect it to the list1 when head1 reaches the end
          if (head2 == null) {
              head2 = list1;
          }
      }
  
      return -1;
  }
}

Output

First Linked List is 4 1 8 4 5
Second Linked List is 5 6 1 8 4 5
The intersection point of two linked lists is: 8

Complexity Analysis: 

  • Time Complexity: O(m + n) 
  • Space Complexity: O(1)

Frequently Asked Questions

What is Floyd’s cycle detection algorithm?

Floyd’s Cycle detection algorithm or Hair Tortoise algorithm detects a cycle in a linked list. It uses two pointers moving through the sequence at different speeds.

How to link two linked lists together?

Two linked lists can be linked together by attaching the head of another list to the tail of the current linked list.

What is the time and space complexity of Floyd’s cycle detection algorithm?

The time complexity is O(N), and the space complexity is O(1) in Floyd’s cycle detection algorithm. Here, “N” represents the number of nodes in the linked list.

What is a linked list?

A Linked List is a linear data structure where the elements called nodes are stored at non-contiguous memory locations.

Explain the approach to convert a singly linked list to a circular linked list?

Traverse the singly linked list, and when the last node is reached, attach it to the head node.

Key Takeaways

This blog covered the various methods to find the intersection point of two linked lists. The methods discussed here are using loops, hashing, the difference of node count, the Floyd cycle detection algorithm, and the two-pointer approach.

Now that you know how to approach a problem in Linked List try out some questions based on them on our CodeStudio Platform!

Don’t stop here. Check out our Data Structures and Algorithms-guided path to learn Data Structures and Algorithms from scratch. We hope you found this blog useful. Feel free to comment down below if you have a better insight into the above approach.

By: Hari Sapna Nair

Exit mobile version