Today we will take a look at a simple question I was asked some years ago when interviewing for an internship! The question is called “Find Intersection Point of 2 Linked Lists in Java”.
Basically, we will try to write a program that takes two Linked Lists as input and will determine the element where the lists intersect. In other words, we will find the first encountered element that is the same for both Linked Lists.
Find Intersection Point of 2 Linked Lists in Java – Assumptions
First of all, let us try to clarify all assumptions. Since the problem refers to Linked Lists we need to know if we are talking about a Singly Linked List, or a Doubly Linked List. Should be obvious, that a doubly linked list would most likely not have an intersection point (unless both lists are the exact same). With that in mind, we can think that the solution should involve a Singly Linked List. Next, let us formalize what that would look like. For now, let us assume we have this Linked List implementation readily available. Lastly, we should clarify input and output. We will assume we cannot modify the input Linked Lists. Also there needs to be clarity on what the output will be, if there is no common element. Let us assume in that case we can simply return null.
After all clarifications are done, we can jump into thinking about the problem. Obviously, a simple brute force approach would be to simply check each element of the first List for each element of the second List. This brute force approach, would run at O(M*N) where M and N are the length of the lists. However, for the purpose of simplicity we can think of it as O(N2) time complexity and assume both lists will be of the same size.
The interviewer most likely, will ask us to do better than that. Let us try to visualize the Lists first.
It can be easily noticed how after the intersection point (M), both lists (A and B) are the same. Therefore, we would know that the longest list will have to have some more unique elements in order for it to intersect with the shorter list.
Find Intersection Point of 2 Linked Lists in Java – Algorithm
- Given index i,j in both lists.
- While the rest of the longest list is longer than the shorter, increase its index.
- Compare each element on the remainder of the lists since their remaining length is the same.
This excellent post on stackoverflow, approaches other optimal solutions, such as changing the List, which we mentioned we cannot. If you want more alternative solutions, check it out!
Back to our algorithms above. Seems like all we have to do now is write down a good implementation that follows our algorithm.
Find Intersection Point of 2 Linked Lists in Java – Implementation
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
package iqLib.LinkedListLib; public class LinkedList { LinkedListNode head; public static void FindIntersectionPoint(LinkedList first, LinkedList second) { int firstRemainingLength = first.getSize(); int secondRemainingLength = second.getSize(); int maxLength = Math.max(firstRemainingLength, secondRemainingLength); LinkedListNode firstCurr = first.head; LinkedListNode secondCurr = second.head; while (firstRemainingLength != 0 && secondRemainingLength != 0) { if (firstRemainingLength > secondRemainingLength) { firstCurr = firstCurr.next; firstRemainingLength--; } elseif (secondRemainingLength > firstRemainingLength) { secondCurr = secondCurr.next; secondRemainingLength--; } else { // Same remaining length if (firstCurr.value == secondCurr.value) { return firstCurr; } } } // No merging point found. return null; } public function getSize() { // Assuming the Linked List doesn't expose size. int size = 0; LinkedListNode curr = head; while (curr != null) { size++; } return size; } } |
Note that in our implementation above, we require the nodes to be the exact same, for the list to be defined as “having an intersection point”. If they instead simply have the same values, then they do not qualify. In fact, that does make sense, since if the lists intersect, we would imagine that changing the value in one of their common nodes, would change the values in both Lists.
Let us analyze the time complexity of this solution to “Find Intersection Point of 2 Linked Lists”. With the Java optimized solution we have, the time complexity will be O(M+N). For let’s mark it O(N), where N is the length of the longest list. Space complexity is O(1) since we did not use any auxiliary space or data structures.
Well it took me about 10 mins to write this down. That means, this question is definitely on the easier side of the spectrum.
Hope you guys enjoyed it… And I’ll see you guys next time ;D
Latest posts by Ajk (see all)
- Find Median from Numbers Array - January 1, 2018
- Find Whether a Number Can Be the Sum of Two Squares - August 12, 2017
- How to Find Two Primes Whose Sum is Equal to a Number N - April 22, 2017