Linked lists are often used to arrange data in a list-like structure. It is mainly made of two components, the first one contains the value or data, and the second one contains the location of the reference to which the pointer of the linked list is pointing next.
These two parts make up the linked list. All the nodes are connected in a straight line in the list in a non-contagious way. Think of it as a chain, with each link containing information and pointing to the next. We can tell the list ends because the final link in the chain points nowhere because it is the end of the list.
They are needed as they help us to add or remove a data item very easily and in less time complexity We can grow and shrink the list without wasting memory. If you want to find something which is present at the end of the list then you need to traverse it individually which takes a little more time.
This article will solve a problem statement based on the link list. Candidates must stick to the article to understand the problem statement and the solution.
Recommended Course
- Decode DSA with C++
- Full Stack Data Science Pro Course
- Java For Cloud Course
- Full Stack Web Development Course
- Data Analytics Course
Problem Statement
You are given two singly linked lists, list A and list B, that intersect at some node. Your task is to write a program to find the value of the node at which the two lists merge. If there is no intersection present between the two lists, then you need to return -1 or not found.
In this problem, you are provided with two linked lists, list A and list B. Each node in the linked list contains an integer value and a reference to the next node. The linked lists may have different lengths and eventually merge, forming a common part.
Linked List A: 1 -> 2 -> 3 -> 4 -> 5
Linked List B: 6 -> 7 -> 8 -> 4 -> 5
No Intersection Condition
Consider a condition in which there is no intersection point in the linked list. In that case you need to return -1 or not found to indicate that there is no common intersection point present in the linked list.
Let us understand this case with an example
Linked List C: 10 -> 20 -> 30
Linked List D: 40 -> 50 -> 60
As we can see in the above linked list C and list D both linked lists do not intersect. After traversing both lists, we find that there is no common part. Therefore, the function would return -1 or not be found as the output.
The Intersection Point Of Two Linked Lists: Using Difference of the Node Counts
In this method, we will traverse the bigger node until both linked list become equal size, then we traverse both until the intersection point is found.
Let us understand the method step by step given here.
- First, we count the number of nodes in each linked list.
- Next, we determine the number of nodes that differ between the two lists.
- If one list is longer than the other, the pointer for the longer list is advanced by the number of extra nodes. This ensures that both lists have the same number of nodes remaining from the intersection point.
- We begin moving both lists together, one step at a time, after the pointers are aligned, and we keep doing this until they either reach the end of the lists or come to a point where they meet.
- If the pointers meet at the same node, we have found the intersection point. We return the value of that node as the answer.
- If the pointers reach the end of their lists without any common point, then it means that there is no intersection between the two lists. In this case, we return -1 to indicate that there is no common part between the lists.
Driver Code
Given here is the driver code for finding the intersection of the linked list.
| The Intersection Point Of Two Linked List: Using Difference of Node Count |
| class ListNode { int val;
ListNode next; ListNode(int val) { this.val = val; } } public class LinkedListIntersection { public static int findIntersection(ListNode headA, ListNode headB) { int lenA = getLength(headA); int lenB = getLength(headB); int diff = Math.abs(lenA – lenB); if (lenA > lenB) { while (diff > 0) { headA = headA.next; diff–; } } else { while (diff > 0) { headB = headB.next; diff–; } } while (headA!= null && headB!= null) { if (headA == headB) { return headA.val; } headA = headA.next; headB = headB.next; } return -1; } private static int getLength(ListNode head) { int length = 0; while (head!= null) { length++; head = head.next; } return length; } |
Main Code
Given here is the main code for finding the intersection of the linked list fr both the example conditions.
| Intersection of Linked List: Main( ) |
| public static void main(String[] args) {
ListNode listA = new ListNode (1); listA.next = new ListNode (2); listA.next.next = new ListNode (3); listA.next.next.next = new ListNode (4); listA.next.next.next.next = new ListNode (5); ListNode listB = new ListNode (6); listB.next = new ListNode (7); listB.next.next = new ListNode (8); listB.next.next.next = listA.next.next.next;
System.out.println ( “Linked List A: “); display.List(listA); System.out.println (“Linked List B: “); displayList(listB); int result = findIntersection(listA, listB); System.out.println(“Example 1 Output: ” + result); //No intersection condition ListNode listC = new ListNode (10); listC.next = new ListNode (20); listC.next.next = new ListNode (30); ListNode listD = new ListNode (40); listD.next = new ListNode (50); listD.next.next = new ListNode (60); int result2 = findIntersection (listC, listD); System.out.println (“Example 2 Output: ” + result2); // Output: -1 } } |
Output:
| Linked List A: 1->2->3->4->5Linked List B: 6->7->8->4->5
Example 1 Output: 4 Example 2 Output: -1 |
Complexity Analysis
Let us do the complexity analysis of this method.
Time Complexity: O(m+n)
Space Complexity: O (1)
The Intersection Point Of Two Linked Lists: Using Hashing
In this method, we will use hashing method to find the intersection point of two linked lists. Let us understand the method step by step given here.
- First, we need to create an empty HashSet data structure.
- Then we will traverse the nodes of the first linked list and add each node to our HashSet.
- In this step, we walk through the nodes of the second linked list. For each node, we check if it already exists in the HashSet.
- If the current node exists in the HashSet, it means we have found the intersection point of the two linked lists. We then return the value of this node as the output of our problem.
- Else, If we reach the end of the second linked list without finding any intersection, then this means the two lists do not intersect.
- In this case, we need to return -1 or not found to indicate that there is no intersection in these linked lists.
Driver Code
Given here is the driver code for finding the intersection of the linked list.
| The Intersection Point Of Two Linked List: Using Hashing |
| import java.util.HashSet;
class ListNode { int val; ListNode next; ListNode(int val) { this.val = val; } } public class LinkedListIntersection { public static int findIntersection(ListNode headA, ListNode headB) { HashSet<ListNode> nodesSet = new HashSet<>(); ListNode tempA = headA; while (tempA!= null) { nodesSet.add(tempA); tempA = tempA.next; } ListNode tempB = headB; while (tempB!= null) { if (nodesSet.contains(tempB)) { return tempB.val; } tempB = tempB.next; } return -1; } } |
Output:
| Linked List A: 1->2->3->4->5Linked List B: 6->7->8->4->5
Example 1 Output: 4 Example 2 Output: -1 |
Complexity Analysis
Let us do the complexity analysis of this method.
Time Complexity: O(m+n)
Space Complexity: O (m+n)
The Intersection Point Of Two Linked Lists: Using Loops
In this method, we will use loops to find the Intersection of Linked lists.
- Here, we are using two nested loops, an outer loop for the first linked list and an inner loop for the second linked list.
- The outer loop selects one node at a time from the first linked list, and the inner loop selects one node at a time from the second linked list.
- Now, we traverse both linked lists simultaneously using these loops until we find an intersection point where both loops select the same node.
- When the two loops reach the same node, then it means we have found the intersection point of the two linked lists.
- Now, return the value of this intersection point of two linked lists as an output.
Driver Code
Given here is the driver code for finding the intersection of the linked list using loops.
| The Intersection Point Of Two Linked List: Using Loops |
| class ListNode {
int val; ListNode next; ListNode(int val) { this.val = val; } } public class LinkedListIntersection { public static int findIntersection(ListNode headA, ListNode headB) { ListNode tempA = headA; ListNode tempB; while (tempA!= null) { tempB = headB; while (tempB!= null) { if (tempA == tempB) { return tempA.val; } tempB = tempB.next; } tempA = tempA.next; } return -1; } |
Output:
| Linked List A: 1->2->3->4->5Linked List B: 6->7->8->4->5
Example 1 Output: 4 Example 2 Output: -1 |
Complexity Analysis
Let us do the complexity analysis of this method.
Time Complexity: O(m*n)
Space Complexity: O (1)
The Intersection Point Of Two Linked Lists
We will use Floyd’s Cycle Detection Algorithm to find the intersection of linked lists under this method.
- We first modify the first linked list by connecting its last node to the first node, then create a circular linked list. This will implement a loop in the first linked list.
- Next, we check if the second linked list contains a loop using Floyd’s Cycle Detection Algorithm.
- We will be using two pointers first one is slow and the second one is fast which will traverse the second linked list.
- If the linked list has a cycle, the slow and fast pointers will eventually meet at the same node.
- If the slow and fast pointers meet, we will set two more pointers.
- One pointer starts at the head of the second linked list, and the other pointer starts at a node that is the same distance from the head as the first linked list’s loop size.
- We then move both pointers at the same speed. The intersection point of the two linked lists is reached when the two pointers cross paths once more.
- Then we will return the value of the current node where the pointers meet as the output.
- The current node is the intersection point of the two linked lists.
- Finally, we break the circular connection to take the loop out of the first linked list.
Driver Code
Given here is the driver code for finding the intersection point of the two linked lists.
| The Intersection Point Of Two Linked Lists: Using Floyd’s Cycle Detection Algorithm |
| public class LinkedListIntersection { private static ListNode findNode (ListNode slow, ListNode list) {
int count = 1; for (ListNode pointer = slow; pointer.next! = slow; pointer = pointer.next) { count++; } ListNode current = list; for (int i = 0; i < count; i++) { current = current.next; } while (current!= list) { current = current.next; list = list.next; } return current; } private static ListNode identifyCycle (ListNode list) { ListNode slow = list, fast = list; while (fast!= null && fast.next!= null) { slow = slow.next; fast = fast.next.next; if (slow == fast) { return slow; } } return null; } public static int intersectionPoint(ListNode list1, ListNode list2) { ListNode previous = null, current = list1; while (current != null) { previous = current; current = current.next; } if (previous != null) { previous.next = list1; } ListNode slow = identifyCycle(list2); ListNode intersectionNode = null; if (slow != null) { intersectionNode = findNode(slow, list2); } if (previous != null) { previous.next = null; } int result = intersectionNode == null ? -1 : intersectionNode.val; return result; } } |
Output:
| Linked List A: 1->2->3->4->5Linked List B: 6->7->8->4->5
Example 1 Output: 4 Example 2 Output: -1 |
Complexity Analysis
Let us do the complexity analysis of this method.
Time Complexity: O(m+n)
Space Complexity: O (1)
The Intersection Point Of Two Linked Lists: FAQs
Q1. What is a linked list data structure?
Ans: A linked list is a way to organize data in a chain structure. Each element in the list contains some information and a reference to the next element in the chain. Linked lists are considered more effective than arrays.
Q2. How do I find the intersection point of two linked lists?
Ans: To find the intersection point of two linked lists, you can use different approaches and choose the one that suits you the most.
- Using Hashing
- Difference of Node counts
- Using Loops
- Using Floyd’s cycle Detection Algorithm
- Using A pointers approach
Complete details on all the methods are given here in this article.
Q3. What happens if the two linked lists have no intersection point?
Ans: If the two linked lists have no intersection, the program will return -1 or “Not Found”.
Q4. Can you find the intersection of linked lists using hashing?
Ans: Yes, a hash set can be used to locate the intersection of linked lists. Check out the complete code for this method in this article.
Q5. What is the significance of Floyd’s Cycle Detection Algorithm in finding the intersection point of two linked lists?
Ans: Floyd’s Cycle Detection Algorithm helps in locating the point where two linked lists intersect by determining whether the second list has a loop. The slow and fast pointers will eventually cross paths at the same node if the linked list has a cycle. The intersection point is where two more pointers are placed and meet.
Recommended Reads
Data Science Interview Questions and Answers
Data Science Internship Programs
