如何将两个有序单链表合并为一个有序列表

Question

我正在尝试合并两个有序的单链列表。我试着寻找问题所在，但我找不到答案。输出结果与我预期的不一样。输出如下所示：

class Test
{
Node head;  // head of list
class Node
{
    int data;
    Node next;
    Node(int d){
        data = d; 
        next = null; 
    }
}

void sortedInsert(Node newNode)
{
     Node current;
     if (head == null || head.data >= newNode.data)
     {
        newNode.next = head;
        head = newNode;
     }
     else {
        current = head;
        while (current.next != null && current.next.data < newNode.data)
            current = current.next;

        newNode.next = current.next;
        current.next = newNode;
     }
 }
 Node newNode(int data)
{
   Node x = new Node(data);
   return x;
}

 /* Function to print linked list */
 void printList()
 {
     Node temp = head;
     while (temp != null)
     {
        System.out.print(temp.data+"-> ");
        temp = temp.next;
     }
     System.out.print("null\n");
 }

 Node mergeLists(Node list1, Node list2) {
    Node result;
    if (list1 == null) return list2;
    if (list2 == null) return list1;
    if (list1.data < list2.data) {
        result = list1;
        result.next = mergeLists(list1.next, list2);
    } else {
        result = list2;
        result.next = mergeLists(list2.next, list1);
    }
    return result;
}

 /* Drier function to test above methods */
 public static void main(String args[])
 {
     Test oneList = new Test();
     Test twoList = new Test();
     Test joinList = new Test();
     Node l1,l2,join;

     //First linked list
     l1 = oneList.newNode(11);
     oneList.sortedInsert(l1);
     l1 = oneList.newNode(13);
     oneList.sortedInsert(l1);
     l1 = oneList.newNode(12);
     oneList.sortedInsert(l1);
     l1 = oneList.newNode(17);
     oneList.sortedInsert(l1);
     l1 = oneList.newNode(15);
     oneList.sortedInsert(l1);
     l1 = oneList.newNode(19);
     oneList.sortedInsert(l1);
     System.out.println("First List");
     oneList.printList();

     //Second Linked List
     l2 = twoList.newNode(1);
     twoList.sortedInsert(l2);
     l2 = twoList.newNode(5);
     twoList.sortedInsert(l2);
     l2 = twoList.newNode(3);
     twoList.sortedInsert(l2);
     l2 = twoList.newNode(7);
     twoList.sortedInsert(l2);
     l2 = twoList.newNode(4);
     twoList.sortedInsert(l2);
     l2 = twoList.newNode(19);
     twoList.sortedInsert(l2);
     System.out.println("Created Second Linked List");
     twoList.printList();

     join=joinList.mergeLists(l1,l2);
     System.out.println("Merge");
     joinList.sortedInsert(join);
     joinList.printList();
 }
 }

产出：

第一份清单

11-> 12-> 13-> 15-> 17-> 19-> null

创建第二链接列表

1-> 3-> 4-> 5-> 7-> 19-> null

合并

19-> null

Answer 1

一个问题是主要的方法。

 oneList.sortedInsert(l1);
 l1 = oneList.newNode(15);
 oneList.sortedInsert(l1);
 l1 = oneList.newNode(19);

l1是list 19 -> NULL，l2 19 -> NULL是相同的。所以合并看起来是正确的，问题是您正在用最后一个元素而不是第一个元素覆盖l1和l2。我希望这能帮到你。

Answer 2

您不想递归地这样做，因为如果列表的大小比较大，那么堆栈就会溢出。合并两个列表是一个简单的迭代操作。其基本思想是：

if (list1 == null) return list2;
if (list2 == null) return list1;

Node head = null;
Node l1 = list1;
Node l2 = list2;

if (l1.data < l2.data)
{
    head = l1;
    l1 = l1.next;
}
else
{
    head = l2;
    l2 = l2.next;
}

Node current = head;
// while not at end of either list
while (l1 != null && l2 != null)
{
    if (l1.data < l2.data)
    {
        current.next = l1;
        l1 = l1.next;
    }
    else
    {
        current.next = l2;
        l2 = l2.next;
    }
    current = current.next;
    current.next = null;
}
// at this point, you are at the end of one or both of the lists
// Pick up the potential remainder from the list that's not at the end.
// Note that only one of these loops will be entered.
while (l1 != null)
{
    current.next = l1;
    current = current.next;
    current.next = null;
    l1 = l1.next;
}
while (l2 != null)
{
    current.next = l2;
    current = current.next;
    current.next = null;
    l2 = l2.next;
}
return head;

这就是简单冗长的解决方案。通过创建一个将节点附加到新列表的方法，可以稍微减少代码的数量，但是逻辑是相同的。