Charan Charan - 1 year ago 98
Java Question

Find Merge Point of Two Lists by reversing the Lists

Problem Statement:
You’re given the pointer to the head nodes of two linked lists that merge together at some node. Find the node at which this merger happens. The two head nodes will be different and neither will be NULL.

Input Format
You have to complete the int FindMergeNode(Node* headA, Node* headB) method which takes two arguments - the heads of the linked lists. You should NOT read any input from stdin/console.

Output Format
Find the node at which both lists merge and return the data of that node. Do NOT print anything to stdout/console.

I am trying to reverse the two lists and then walk through each of them seperately until I reach the last common node. But when tested, it's not giving the correct ouput.
Is my thinking wrong or my code wrong? Is this a good approach or a bad one?


int FindMergeNode(Node headA, Node headB) {

//Reverse listA
Node currentA = headA;
Node prevA = null;
Node NextA;
NextA =; = prevA;
prevA = currentA;
currentA = NextA;
headA = prevA;

//Reverse listB
Node currentB = headB;
Node prevB = null;
Node NextB;
NextB =; = prevB;
prevB = currentB;
currentB = NextB;
headB = prevB;

//Iterate throught the reversed list and find the last common node.
Node n = headA;
Node m = headB;
n =;
m =;


Link to question:

Edit: From karthik's answer, I modified the third while loop, but still it is giving the wrong output.

//Iterate throught the reversed list and find the last common node.
Node n = headA;
Node m = headB;
while( =={
n =;
m =;


Answer Source

Edit: you should have been more clear with your explanation. Because by merge if you meant merging of values, reversing approach works. But if you meant merging of actual nodes, obviously reversing approach does not work because when you reverse the list the merging point can have only next pointer.


If this was your list, when you reverse you certainly cant have both C and Y as your next pointer.Because when you reverse your tree will become

                       I<-J<- K
                X <-Y

But your I will point to either Y or C depending on which is reversed later.

Another easier approach(implementation wise) would be to push the nodes in to two stacks and once you finish all the nodes start poping the elements and return the last node which was same.

 Stack<Node> stackA - push all elements of listA into stackA;
 Stack<Node> stackB - push all elements of listB into stackA;

 Node result=null;
 while(stackA.peek() == stackB.peek()){
    result = stackA.pop();
 return result;

Below explanation answers your original question

I did not check your reversing the list logic, but your while loop after that(3rd while loop) is certainly wrong :

     n =;
     m =;

The main point is - it should be ==

  // ideally you should also check (n!=null && m!=null) 
  // it handles the case where there is no common point
  while(n!=null && m!=null && =={
     n =;
     m =;
 return (n == null || m == null)? null : n;

because you want to find the first node that is different and return the previous node.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download