Given pointers to the head nodes of linked lists that merge together at some point, find the Node where the two lists merge. It is guaranteed that the two head Nodes will be different, and neither will be NULL.
We need to find the merging point of two linked lists.
Let's first solve this problem using stacks :
We will push all elements of list1 in stack1 and all elements of list2 in stack2. While popping each element we will compare and if it is different we will return the just previously traversed Node. i.e the node from where diversion occurred.
Java solution for the above problem is as below:
package askgif.linkedlist;
import java.util.Stack;
class ListNode{
public int data;
public ListNode next;
ListNode(int data){
this.data = data;
}
};
public class CircularNodeExist {
public static void main(String[] args) {
ListNode node1 = new ListNode(1);
ListNode node2 = new ListNode(2);
ListNode node3 = new ListNode(3);
ListNode node4 = new ListNode(4);
ListNode node5 = new ListNode(5);
ListNode node6 = new ListNode(6);
ListNode node7 = new ListNode(7);
ListNode node8 = new ListNode(8);
ListNode node9 = new ListNode(9);
ListNode node10 = new ListNode(10);
ListNode node11 = new ListNode(11);
node4.next = node5;
node5.next = node6;
node6.next = node7;
node7.next = node8;
node8.next = node9;
node9.next = node10;
node10.next = node11;
node11.next = null;
node1.next = node2;
node2.next = node3;
node3.next = node8;
System.out.println(GetMeetingNode( node1, node4));
}
private static int GetMeetingNode(ListNode node1, ListNode node2) {
//By using stack
Stack<ListNode> stack1 = new Stack<ListNode>();
Stack<ListNode> stack2 = new Stack<ListNode>();
while(node1 != null) {
stack1.push(node1);
node1 = node1.next;
}
while(node2 != null) {
stack2.push(node2);
node2 = node2.next;
}
ListNode prev = null;
while(!stack1.isEmpty() && !stack2.isEmpty()){
ListNode data1 = stack1.pop();
ListNode data2 = stack2.pop();
if(data1 != data2)
return prev.data;
prev = data1;
}
return -1;
}
}
output:
8The time complexity of the above solution is O(n) for traversing the Linked List While Space complexity is O(n) since we are using a stack to store the nodes.
Can we do it better?
Yes by using length property.
calculate the difference of both list length. Traverse the Larger linked list by k(difference) steps. then just compare both nodes. if they are equal just return the data of the node.
Java Solution is as below:
package askgif.linkedlist;
import java.util.Stack;
class ListNode{
public int data;
public ListNode next;
ListNode(int data){
this.data = data;
}
};
public class CircularNodeExist {
public static void main(String[] args) {
ListNode node1 = new ListNode(1);
ListNode node2 = new ListNode(2);
ListNode node3 = new ListNode(3);
ListNode node4 = new ListNode(4);
ListNode node5 = new ListNode(5);
ListNode node6 = new ListNode(6);
ListNode node7 = new ListNode(7);
ListNode node8 = new ListNode(8);
ListNode node9 = new ListNode(9);
ListNode node10 = new ListNode(10);
ListNode node11 = new ListNode(11);
node4.next = node5;
node5.next = node6;
node6.next = node7;
node7.next = node8;
node8.next = node9;
node9.next = node10;
node10.next = node11;
node11.next = null;
node1.next = node2;
node2.next = node3;
node3.next = node8;
System.out.println(GetMeetingNode( node1, node4));
}
private static int GetMeetingNode(ListNode node1, ListNode node2) {
//By using length property
int len1=0;
int len2=0;
ListNode ll1 = node1;
ListNode ll2 = node2;
while(node1 != null) {
len1++;
node1 = node1.next;
}
while(node2 != null) {
len2++;
node2 = node2.next;
}
if(len1 > len2) {
int diff = len1 - len2;
int i = 0;
while(ll1 != null && i != diff) {
i++;
ll1 = ll1.next;
}
}
else
{
int diff = len2 - len1;
int i = 0;
while(ll2 != null && i != diff) {
i++;
ll2 = ll2.next;
}
}
while(ll1 != null) {
if(ll1 == ll2)
return ll1.data;
ll1 = ll1.next;
ll2 = ll2.next;
}
return -1;
}
}
output:
8The time complexity of the above solution is O(1) and the space complexity is also O(1).
