通过颠倒列表查找两个列表的合并点

Question

问题描述： 给出指向两个链接列表的头节点的指针，这两个链接列表在某个节点上合并在一起。找到发生此合并的节点。两个头节点将会不同，都不会为NULL。

输入格式 您必须完成int FindMergeNode（Node * headA，Node * headB）方法，该方法接受两个参数 - 链接列表的头部。你不应该读取标准输入/控制台的任何输入。

输出格式 查找两个列表合并并返回该节点的数据的节点。不要将任何东西打印到标准输出/控制台。

我想扭转这两个列表，然后分别走过他们每个人，直到我到达最后一个公共节点。但是在测试时，它没有给出正确的输出。 我的想法是错的还是我的代码错了？这是一个好方法还是坏方法？

我的代码：

int FindMergeNode(Node headA, Node headB) { 

//Reverse listA 
Node currentA = headA; 
Node prevA = null; 
Node NextA; 
while(currentA!=null){ 
    NextA = currentA.next; 
    currentA.next = prevA; 
    prevA = currentA; 
    currentA = NextA; 
} 
headA = prevA; 

//Reverse listB 
Node currentB = headB; 
Node prevB = null; 
Node NextB; 
while(currentB!=null){ 
    NextB = currentB.next; 
    currentB.next = prevB; 
    prevB = currentB; 
    currentB = NextB; 
} 
headB = prevB; 

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

return n.data; 
} 

链接问题：https://www.hackerrank.com/challenges/find-the-merge-point-of-two-joined-linked-lists

编辑：从KARTHIK的回答，我修改了第三while循环，但它毕竟是给了错误的输出。

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

return n.data; 

Answer 1

编辑：你应该已经更加明确你的解释。因为通过merge，如果你的意思是合并价值，倒车方法的作品。但是如果你的意思是合并实际节点，显然反转方法不起作用，因为当你反转列表时，merging point只能有下一个指针。

A->B->C 
      \ 
      I->J->K 
     /
    X->Y 

如果这是你的列表中，当你扭转你可不能兼得C和Y当你扭转你的下一个pointer.Because你的树将成为

   A<-B<-C 
         I<-J<- K 
       X <-Y 

但是你I将指向取决于哪一个在后面被逆转，可以是Y或C。

另一种更简单的方法（实施方式）将其推入节点两个stack S和一旦你完成所有的节点开始pop荷兰国际集团的元素，并返回这是相同的最后一个节点。

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(); 
    stackB.pop(); 
} 
return result; 

下面的解释回答你原来的问题

我没有检查你的reversing the list逻辑，但（3 while环）后while循环肯定是错误的：

while(n.next!=m.next){ 
    n = n.next; 
    m = m.next; 
} 

的要点 - 它应该是n.next == m.next

// 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.next == m.next){ 
    n = n.next; 
    m = m.next; 
} 
return (n == null || m == null)? null : n; 

，因为你想找到不同的第一个节点并返回前一个节点。

Answer 2

我也有从here这个问题，我最快的解决方案：

int FindMergeNode(Node headA, Node headB) { 
    int s1 = getSize(headA), s2 = getSize(headB); 
    for(int i = 0; i<Math.abs(s1-s2); i++){ 
     if(s1>s2) headA = headA.next; 
     else headB = headB.next; 
    } 
    while(headA!=null){ 
     if(headA==headB) return headA.data; 
     headA = headA.next; 
     headB = headB.next; 
    } 
    return 0; 

} 
int getSize(Node head){ 
    int i = 0; 
    while(head!=null){ 
     head = head.next; 
     i++; 
    } 
    return i; 
}