Kind of data structure questions which are normal in C language because C has pointers, so we have address of each memory location. But when we take java into consideration we don't have any pointer to judge whether nodes are same or not except double equal check( i.e. reference check). And then java.util.collections package comes to rescue us.
2. Main class where intersection logic written:
Output:
That's all from my end on this post. As there can be a number of ways by which you can solve this problem, looking forward for your contribution. Thanks.
There are a number of ways by which you can solve the problem but important things are time and space complexity. It matters a lot when you are designing a highly scalable system where performance matters a lot and other side of story is "space comes at premium" which cannot be ignored.
Now let me put the problem statement into diagrammatic representation so that it would be easy to understand.
So here intersecting node is 45 which is first common element in both the linked list.
Time to start with my version of solution which is not very good from space complexity point of view but takes linear time complexity.
Before we start a very good point about IdentityHashMap is that it does reference matching i.e. double equals check not .equals() matching. So we are going to take this advantage in our algorithm.
Alogrithm steps:
1. Create an IndentityHashMap.
2. iterate through list 1 and put all nodes as key into IdentityHashMap.
3. iterate through list 2 and do containsKey check for all nodes in list2. Which ever containsKey returns true is the intersecting node between 2 linked list.
Time Complexity: O(n + m) linear order where n= elements in list1 and m= elements in list2
Space Complexity: O(n) linear order where n = elements in list1.
So far we are done with our algorithm design and need to jump start with code:
1. Below is pojo class which represents individual node in linked list.
public class Node<T> {
private T value;
private Node<T> next;
public T getValue() {
return value;
}
public void setValue(T value) {
this.value = value;
}
public Node<T> getNext() {
return next;
}
public void setNext(Node<T> next) {
this.next = next;
}
}
2. Main class where intersection logic written:
import java.util.IdentityHashMap;
import java.util.Map;
public class IntersectionExample {
public static void main(String[] args) {
Node<Integer> list1 = new Node<Integer>();
list1.setValue(20);
Node<Integer> node1 = new Node<Integer>();
node1.setValue(60);
Node<Integer> node2 = new Node<Integer>();
node2.setValue(90);
Node<Integer> node3 = new Node<Integer>();
node3.setValue(45);
Node<Integer> node4 = new Node<Integer>();
node4.setValue(23);
node4.setNext(null);
list1.setNext(node1);
node1.setNext(node2);
node2.setNext(node3);
node3.setNext(node4);
Node<Integer> list2 = new Node<Integer>();
list2.setValue(9);
Node<Integer> point1 = new Node<Integer>();
point1.setValue(5);
Node<Integer> point2 = new Node<Integer>();
point2.setValue(8);
list2.setNext(point1);
point1.setNext(point2);
point2.setNext(node3);
getIntersection(list1, list2);
}
public static void getIntersection(Node<Integer> list1, Node<Integer> list2){
final Integer constant = 1;
Map<Node<Integer>, Integer> map = new IdentityHashMap<Node<Integer>, Integer>();
while(list1 != null){
Node<Integer> current = list1;
map.put(current, constant);
list1 = list1.getNext();
}
while(list2 != null){
Node<Integer> current = list2;
if(map.containsKey(current)){
System.out.println("Intesecting Node, value: "+current.getValue());
break;
}
list2 = list2.getNext();
}
}
}
Output:
Intesecting Node, value: 45
That's all from my end on this post. As there can be a number of ways by which you can solve this problem, looking forward for your contribution. Thanks.
