我有一个关于我正在参加的编码类(class)的期末复习的问题。它要求将 3 个链表合并为 1 个链表。我遇到的问题是在合并列表时，我能够按升序合并三个列表，但我缺少第二个列表 23 和 25 的最后两个节点。我无法弄清楚为什么它停在那里。问题在这里:

编写一个名为 LinkedTest 的程序:

1. 创建三个排序的整数单链表，如下所示

First List:  2 11 19 21 24

Second List: 14 15 18 23 25

Third List:  3 9 17 20 22

1. 将三个链表合并为一个新的排序链表，如下所示:2 3 9 11 14 15 17 18 19 20 21 22 23 24 25
2. 返回新的排序链表 要求:你的程序的时间复杂度必须小于等于O(nlog n)

这是我的代码:

public class LinkedTest {

public static class ListNode {

    private int data;
    ListNode next;

    public ListNode(int data) {
        this.data = data;
        next = null;
    }
}

ListNode head;

public static void main(String[] args) {

    LinkedTest list = new LinkedTest();

        int[] data1 = { 2, 11, 19, 21, 24 };

        ListNode head1 = new ListNode(data1[0]);

        for (int i = 1; i < data1.length; i++)
            list.push(head1, data1[i]);

        System.out.print("First List: ");
        list.display(head1);

        int[] data2 = { 14, 15, 18, 23, 25 };

        ListNode head2 = new ListNode(data2[0]);

        for (int count = 1; count < data2.length; count++)
            list.push(head2, data2[count]);

        System.out.println(" Second List: ") ;

        list.display(head2);

        int[] data3 = { 3, 9, 17, 20, 22 };

        ListNode head3 = new ListNode(data3[0]);

        for (int count = 1; count < data3.length; count++)
            list.push(head3, data3[count]);

        System.out.println(" Third List: ") ;

        list.display(head3);

        ListNode n = list.LinkedTest(head1, head2, head3);

        System.out.print(" Merged List: ");

        list.display(n);
    }



public ListNode LinkedTest(ListNode first, ListNode second, ListNode third) { 
      ListNode head = null;

        if (first == null && second != null && third != null)

            return second;

        else if (second == null && third != null && first != null)

            return third;

        else if (third == null && first != null && second != null)

            return first;

        else if (first.data < second.data && first.data < third.data) 
        {
            head = first;
            head.next = LinkedTest(first.next, second, third);
        } 
        else if (second.data < third.data && second.data < first.data)
        {
            head = second;
            head.next = LinkedTest(first, second.next, third);
        }

        else if (third.data < first.data && third.data < second.data)
        {
            head = third;
            head.next = LinkedTest(first, second, third.next);
        }

        return head;
    }

    public void push(ListNode head, int n) 
    {
        while (head.next != null)
            head = head.next;
        head.next = new ListNode(n);
    }

    public void display(ListNode head)
    {
        ListNode tempDisplay = head; 
        while (tempDisplay != null) 
        {
            System.out.print(tempDisplay.data);
            tempDisplay = tempDisplay.next; 
    }

    }
}

输出:

First List:   2 11 19 21 24 
Second List:  14 15 18 23 25 
Third List:   3 9 17 20 22 
Merged List:  2 3 9 11 14 15 17 18 19 20 21 22 24

最佳答案

为什么要限制自己使用 3 向合并？让我们看看 N 路合并的一般情况，然后将其应用到 3 路(或普通的旧无聊 2 路)。

// drop-in replacement for your LinkedTest(), but I like the name better:
// ListNode n = list.merge(head1, head2, head3);
public ListNode merge(ListNode... nodes) {

    // find smallest, keep its index
    int firstIndex = -1;
    int firstValue = 0;
    for (int i=0; i<nodes.length; i++) {
        ListNode n = nodes[i];
        if (n != null && (firstIndex == -1 || n.data < firstValue)) {
            firstIndex = i;
            firstValue = n.data;
        }
    }

    if (firstIndex == -1) {
        // reached the end of all lists
        return null;
    } else {
        // use node with smallest as next head
        ListNode head = nodes[firstIndex];

        // call again with all lists, but skipping head
        // because we are already using it in the result list
        nodes[firstIndex] = head.next;
        head.next = merge(nodes);
        return head;
    }
}

你可以把它看成许多链条，链条上有数字，每条链条的数字按升序排列。要按顺序构建所有数字的大链，您:

• 捕获剩余链条的所有小端
• 选择最小的链接(如果没有剩下，你就完成了)
• 将该链接从其链中删除，并将其添加到新链的末尾
• 返回选择旧链条的最小链节

正如 Jacob_G 所指出的，在您的回答中，您缺少一些在一个或多个列表为空时选择正确的最小元素的逻辑。雅各布的回答很好，但我想向你展示更大的图景:如果你理解 N，3 应该没有延伸(另外，你会深入了解总体思路)。

关于java - 将 3 个链表合并为 1 个(Java)，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/53843597/