这是我的第一个自己ak的分治题目!!!好耶!!(骄傲脸文章来源:https://www.toymoban.com/news/detail-792481.html
思路参考:148. 排序链表(归并排序)文章来源地址https://www.toymoban.com/news/detail-792481.html
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
return dfs(lists, 0, lists.length - 1);
}
public ListNode dfs(ListNode[] lists, int head, int tail) {
if (head > tail) return null;
if (head == tail) return lists[head];
int mid = (head + tail) / 2;
ListNode node1 = dfs(lists, head, mid);
ListNode node2 = dfs(lists, mid + 1, tail);
ListNode node = merge(node1, node2);
return node;
}
public ListNode merge(ListNode node1, ListNode node2) {
ListNode node = new ListNode(0);
ListNode temp = node, temp1 = node1, temp2 = node2;
while (temp1 != null && temp2 != null) {
if (temp1.val < temp2.val) {
temp.next = temp1;
temp1 = temp1.next;
} else {
temp.next = temp2;
temp2 = temp2.next;
}
temp = temp.next;
}
if (temp1 != null) temp.next = temp1;
if (temp2 != null) temp.next = temp2;
return node.next;
}
}
到了这里,关于23. 合并 K 个升序链表(递归分治)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!