java - 合并两个不等长的排序链表

Question

我正在尝试合并两个已排序的链表。

代码片段不适用于以下两个列表:

List 1 : 1->3->5->7->9->null
List 2 : 2->4->6->8->10->null

Expected List : 1->2->3->4->5->6->7->8->9->10->null

但是下面程序的输出结果是这样的:

Output :  1->2->3->4->5->6->7->8->9->null // element 10 is missing.

我错过了什么吗？现场演示:http://ideone.com/O7MBlo

class Node {

    Node next;
    int value;

    Node(int val) {
        this.value = val;
        this.next = null;
    }

    @Override
    public String toString() {
        Node cur = this;
        String str = "";

        while(cur != null) {
            str += cur.value+"->";
            cur = cur.next;
        }

        return str;
    }
}

class MergeLL {

    public static Node merge(Node n1, Node n2) {

        Node result = null;

        if(n1 != null && n2 != null) {
            if(n1.value < n2.value) {
                result = n1;
                result.next = merge(n1.next, n2);
            } else {
                result = n2;
                result.next = merge(n1, n2.next);
            }
        }
        return result;
    }

    public static void main(String[] args) {
        Node n1 = new Node(1);
        Node n3 = new Node(3);
        Node n5 = new Node(5);
        Node n7 = new Node(7);
        Node n9 = new Node(9);

        n1.next = n3;
        n3.next = n5;
        n5.next = n7;
        n7.next = n9;
        n9.next = null;

        Node n2 = new Node(2);
        Node n4 = new Node(4);
        Node n6 = new Node(6);
        Node n8 = new Node(8);
        Node n10 = new Node(10);

        n2.next = n4;
        n4.next = n6;
        n6.next = n8;
        n8.next = n10;
        n10.next = null;

        System.out.println("Merge : " + merge(n1, n2));
    }
}

Answer 1

您需要再添加两个条件，以便 n1 或 n2 提前耗尽。因此，您的条件 - n1 != null && n2 != null 仅适用于两个列表大小相同的情况。

只需为以下两个条件添加代码，之后如果:

if(n1 != null && n2 != null) {
        if(n1.value < n2.value) {
            result = n1;
            result.next = merge(n1.next, n2);
        } else {
            result = n2;
            result.next = merge(n1, n2.next);
        }

} else if (n1 != null) {  
    result = n1;  // Add all the elements of `n1` to `result`
} else if (n2 != null) {
    result = n2;  // Add all the elements of `n2` to `result`
}

---

实际上，您不需要在那里构建一个新的result 列表。您可以简单地扩展传递的节点之一。

您可以修改您的方法如下:

public static Node merge(Node n1, Node n2) {
    if (n1 == null) return n2;
    if (n2 == null) return n1;

    if (n1.value < n2.value) {
        n1.next = merge(n1.next, n2);
        return n1;
    } else {
        n2.next = merge(n2.next, n1);
        return n2;
    }
}