我有一个关于编程课程的最终审查问题。它要求将3个链表合并为1个链表。当我尝试按升序合并三个链表时，我发现少了第二个链表中的最后两个节点23和25。我不知道为什么会停在那里。题目如下：
编写一个名为LinkedTest的程序，该程序应该：
- 创建三个按顺序排列的整数单向链表，如下所示
First List: 2 11 19 21 24
Second List: 14 15 18 23 25
Third List: 3 9 17 20 22
- 将三个链表合并成一个新的有序链表，如下所示：
2 3 9 11 14 15 17 18 19 20 21 22 23 24 25 - 返回新的有序链表 要求：您的程序时间复杂度必须小于或等于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
int[] data3 = { 3, 9, 17, 20, 22 };输出第三个列表：149172022在你理解这部分之前不要考虑合并。 - Scary Wombat