合并两个排序的链表

Question

我在逻辑上有错误，我正在尝试使用递归进行合并。请指导我哪里错了。

输入（标准输入）：

4

1 3 5 6

3

2 4 7

我的输出（标准输出）： 1 3 5 6

预期输出： 1 2 3 4 5 6 7

 /*
  Node is defined as 
  class Node {
     int data;
     Node next;
  }
*/

Node mergeLists(Node headA, Node headB) {
    if(headA==null)
    {
        return headB;
    }
    if(headB==null)
    {
        return headA;
    }
    if(headA.data<headB.data)
    {  
        headA.next=mergeLists(headA.next,headB.next);
        return headA;
    }
    else{

        headB.next=mergeLists(headA.next,headB.next);
        return headB;
    }

}

Answer 1

您正在推进两个列表，而您应该只推进其中一个。

Node mergeLists(Node headA, Node headB) {
    if(headA==null)
    {
        return headB;
    }
    if(headB==null)
    {
        return headA;
    }
    if(headA.data<headB.data)
    {  
        headA.next=mergeLists(headA.next,headB); // Note change here, using only smallest
        return headA;
    }
    else{

        headB.next=mergeLists(headA,headB.next); // Note change here, using only smallest
        return headB;
    }
}