题目描述:
给你一个链表数组,每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中,返回合并后的链表。
题目解答:
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
if (list1 == null || list2 == null)
return list1 == null ? list2 : list1;
if (list1.val < list2.val) {
list1.next = mergeTwoLists(list1.next, list2);
return list1;
} else {
list2.next = mergeTwoLists(list1, list2.next);
return list2;
}
}
public ListNode mergeKLists(ListNode[] lists) {
int len = lists.length;
if (len == 0)
return null;
while (len > 1) {
for (int i = 0; i < len / 2; i++)
lists[i] = mergeTwoLists(lists[i], lists[len - 1 - i]);
len = (len + 1) / 2;
}
return lists[0];
}
}
题目思路:
本题的思路可以袭承自【力扣刷题练习】21. 合并两个有序链表中的递归解法
将C++的合并处理
public:
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
if(list1==nullptr||list2==nullptr)
return list1==nullptr?list2:list1;
if(list1->val<list2->val){
list1->next=mergeTwoLists(list1->next,list2);
return list1;
}
else{
list2->next=mergeTwoLists(list1,list2->next);
return list2;
}
}
转换为Java下的合并操作
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
if (list1 == null || list2 == null)
return list1 == null ? list2 : list1;
if (list1.val < list2.val) {
list1.next = mergeTwoLists(list1.next, list2);
return list1;
} else {
list2.next = mergeTwoLists(list1, list2.next);
return list2;
}
}
接下来在主函数中设计实现将该list组两两合并,直到不能再合并为止则认为合并链表完成,最后返回首位的链表数组元素。