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:
- Initialize an outer loop for the first linked list.
- Initialize the inner loop for the second linked list.
- Traverse the linked lists till the intersecting node is met.
- 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:
- Create an empty HashSet.
- Traverse the first linked list and store all the nodes.
- Traverse the second linked list and store the nodes till the intersecting node is met.
- 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:
- Find the size of linked lists.
- Calculate the difference (d) in the sizes of the linked list.
- Swap the linked list to make the first linked list larger (if required).
- Traverse the bigger list till d.
- 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:
- Convert the first linked list into a circular linked list.
- Detect if a cycle is present.
- Set two pointers: one at the head of the loop and the other at the kth node.
- Simultaneously move the list and current pointers at the same speed until they meet.
- Return the current value, which is the value of the intersecting node.
- 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:
- Initialize two pointers head1 and head2, at the head of list1 and list2, respectively.
- Traverse through the linked lists
- When head1 reaches the end of a list, then assign it to list2.
- When head2 reaches the end of a list, then assign it to list1.
- When both of them are reassigned, they will be equidistant from the intersection point.
- 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
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.
Two linked lists can be linked together by attaching the head of another list to the tail of the current linked list.
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.
A Linked List is a linear data structure where the elements called nodes are stored at non-contiguous memory locations.
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
Leave a Reply