通过反转列表找到两个列表的合并点

Question

问题陈述：您将获得指向两个链表的头节点的指针，这两个链表在某个节点处合并在一起。查找发生此合并的节点。两个头节点将不同，并且都不会为 NULL。

输入格式您必须完成带有两个参数的 int FindMergeNode(Node* headA, Node* headB) 方法 - 链表的头部。您不应该阅读来自 stdin/console.

的任何输入

输出格式找到两个列表合并的节点和 return 该节点的数据。不要将任何内容打印到 stdout/console.

我试图颠倒这两个列表，然后分别遍历每个列表，直到到达最后一个公共节点。但是在测试时，它没有给出正确的输出。是我的思路错了还是我的代码错了？这是好方法还是坏方法？

我的代码：

 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;
}

Link 提问：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，一旦完成所有节点就开始 pop ing 元素和 return 相同的最后一个节点。

 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 逻辑，但是你的 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;

因为您想找到第一个不同的节点和 return 前一个节点。

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;
}

通过反转列表找到两个列表的合并点

Find Merge Point of Two Lists by reversing the Lists

java

merge

linked-list

nodes

data-structures