Java合并两个及以上有序链表的示例详解
在Java中,合并两个及以上有序链表是一种常见且重要的操作。下面将详细介绍实现此操作的步骤以及示例。
实现步骤
- 定义一个新的链表,作为合并后的有序链表。
- 比较两个链表的首元素大小,并将较小的元素添加到新链表末尾。
- 重复步骤2,直至两个链表中至少有一个为空。
- 将非空的链表剩余元素添加到新链表末尾。
示例说明
示例1
输入链表1:1 -> 2 -> 4
输入链表2:1 -> 3 -> 4
合并后的有序链表:1 -> 1 -> 2 -> 3 -> 4 -> 4
我们可以使用编写一个Java函数来实现以上的步骤。
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(-1);
ListNode cur = dummy;
while (l1 != null && l2 != null) {
if (l1.val <= l2.val) {
cur.next = l1;
l1 = l1.next;
} else {
cur.next = l2;
l2 = l2.next;
}
cur = cur.next;
}
if (l1 == null) {
cur.next = l2;
} else {
cur.next = l1;
}
return dummy.next;
}
在这个函数中,我们使用了一个dummy节点作为新链表的头节点,然后比较l1和l2的首元素大小,并将较小的元素添加到新链表的末尾。最后,如果l1或l2中还有剩余元素,我们将它们加到新链表的末尾。
示例2
输入链表1:1 -> 2 -> 3 -> 4
输入链表2:null
输入链表3:1 -> 2 -> 5 -> 6
合并后的有序链表:1 -> 1 -> 2 -> 2 -> 3 -> 4 -> 5 -> 6
我们还可以扩展该函数,将多个有序链表合并。
public ListNode mergeKLists(ListNode[] lists) {
if (lists.length == 0) {
return null;
}
int interval = 1;
while (interval < lists.length) {
for (int i = 0; i < lists.length - interval; i = i + 2 * interval) {
lists[i] = merge(lists[i], lists[i + interval]);
}
interval *= 2;
}
return lists[0];
}
public ListNode merge(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(-1);
ListNode cur = dummy;
while (l1 != null && l2 != null) {
if (l1.val <= l2.val) {
cur.next = l1;
l1 = l1.next;
} else {
cur.next = l2;
l2 = l2.next;
}
cur = cur.next;
}
if (l1 == null) {
cur.next = l2;
} else {
cur.next = l1;
}
return dummy.next;
}
在这个函数中,我们先根据传入的链表数组长度判断数组是否为空,并将间隔interval初始化为1。然后,通过两层循环遍历链表数组,每次取出i和i+interval位置上的链表进行合并,直到遍历完整个链表数组。我们也是利用了之前编写的merge函数来合并两个链表。
本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:Java合并两个及以上有序链表的示例详解 - Python技术站