java - 如何改进我在 Java 中合并两个排序链接列表的代码

Question

我通过电子邮件收到了微软的面试问题，很简单，只需合并两个排序的链表并确保没有相同的数据。

我用Java实现了它：

https://gist.github.com/cb4cd94f74cff1d2bd03

起初我想使用递归，但我认为当列表太大时它效率不高。所以我改用while。

但是当我把它发回去时，没有任何回应了，所以我想知道我的代码有什么问题吗？我应该如何改进它？

谢谢 ！

Answer 1

您正在检查其中一个列表是否null被RuntimeException抛出？我认为，如果其中一个列表是null而另一个不是，您可以返回第二个。我错过了什么吗？无论如何，如果输入不符合您的预期，则没有理由 throw RuntimeException，更InvalidArgumentException适合。

if (head1 == null || head2 == null) {
        throw new RuntimeException(
                "Unavaliable source data sets, please make sure both of the two lists are not null");
    }

此外，您的代码不是最优的。我会选择更简洁的东西：（注意使用访问器方法而不是直接访问Node类成员——这被认为是不好的，因为你破坏了封装）

Node MergeLists(Node list1, Node list2) {
    if (list1 == null) {
       return list2;
    } 
    if (list2 == null) {
        return list1;
    }  

    if (list1.getData() < list2.getData()) {
        list1.setNext(MergeLists(list1.getNext(), list2));
        return list1;
    } else {
        if (list1.getData() != list2.getData()) {
            list2.setNext(mergeLists(list2.getNext(), list1));
            return list2;
        }

        Node tail = mergeLists(list2.getNext(), list1.getNext());
        tail = (tail == null) ? null : tail.getNext();

        list2.setNext(tail);
        return list2;
    }
}

Answer 2

Stefan Haustein 在另一个帖子中解决了这个问题！

采访：合并两个排序的单链表

public static Node merge(Node list1, Node list2) {
    if (list1 == null)
        return list2;
    if (list2 == null)
        return list1;

    Node head;
    if (list1.data < list2.data) {
        head = list1;
    } else {
        head = list2;
        list2 = list1;
        list1 = head;
    }
    while (list1.next != null && list2 != null) {
        if (list1.next.data <= list2.data) {
            list1 = list1.next;
        } else {
            Node tmp = list1.next;
            list1.next = list2;
            list2 = tmp;
        }
    }
    if (list1.next == null)
        list1.next = list2;
    return head;
}

Answer 3

你可以改进你的算法来解释这样的列表：

 1 -> 4 -> 6 -> 8  -> 12
 2 -> 3 -> 9 -> 10 -> 19

用你的算法：

1:    1 -> 2 -> 4 -> 6 -> 8 -> 12        Node1: 1, Node2: 2
2:    1 -> 2 -> 3 -> 4 -> 6 -> 8 -> 12   Node1: 2, Node2: 3
3:    1 -> 2 -> 3 -> 4 -> 6 -> 8 -> 12   Node1: 3, Node2: 9  
...

使用优化算法，您会看到 2 -> 3 将适合 1 -> 4 并将 1 指向 2 和 3 指向 4。正是这组指令使它如此：

 ...
 tmp = head2.next;
 head2.next = head1.next;
 head1.next = head2;
 head2 = tmp;
 head1 = head1.next;
 ...

见你设置head1.next = head2然后 2 行后你设置head1 = head1.next。

此外，阅读并试图确定节点到节点发生了什么真的很困难。你的评论没有用。也许像//swap the nodes.

您的 while 循环可以使用退出条件。多个出口点不是很好的风格。无限循环是一个很大的禁忌，它们使理解/绘制代码变得更加困难。

希望这可以帮助。

编辑：这就是我想出的。

public static Node merge(Node node1, Node node2){
    //store head to be returned (the smallest)
    Node masterHead = node1.value > node2.value? node2 : node1;
    //put smaller elements at the beginning
    while(node1 != null && node2.next != null && node1.value > node2.value)
    {   
        Node nextInList2 = node2.next;
        node2.next = node1;
        node1 = node2;
        node2 = nextInList2;
    }
    //merging loop
    while(node1.next != null && node2 != null){
        if(node1.next.value > node2.value)
        {
            //insert node(s) into the array
            Node higherNode = node1.next;
            node1.next = node2;
            //advance until every node being inserted is less that the next
            while(node2.next != null && higherNode.value > node2.next.value){
                node2 = node2.next;
            }
            //point back into the list
            Node nextInList2 = node2.next;
            node2.next = higherNode;
            node2= nextInList2;
        }
        node1 = node1.next;
    }
    if(node1.next == null)
        node1.next = node2;
    return masterHead;
}

我没有测试空参数，只是因为假设/我没有把它变成微软。

Answer 4

这是一个解决方案

Public static void merge(Node first, Node second){
    if(first==null) return second;
    if(second==null) return first;

    if(first.data<second.data){
        first.next = merge(first.next, second);
        return first;
    }else{
        second.next = merge(second.next, first);
        return second;
    }
}