#yyds干货盘点# 面试必刷TOP101：合并k个已排序的链表

#yyds干货盘点# 面试必刷TOP101：合并k个已排序的链表

1.简述：

描述

合并 k 个升序的链表并将结果作为一个升序的链表返回其头节点。

示例1

输入：

[{1,2,3},{4,5,6,7}]

返回值：

{1,2,3,4,5,6,7}

示例2

输入：

[{1,2},{1,4,5},{6}]

返回值：

{1,1,2,4,5,6}

2.代码实现：

import java.util.ArrayList;public class Solution { //两个链表合并函数 public ListNode Merge(ListNode list1, ListNode list2) { //一个已经为空了，直接返回另一个 if(list1 == null) return list2; if(list2 == null) return list1; //加一个表头 ListNode head = new ListNode(0); ListNode cur = head; //两个链表都要不为空 while(list1 != null && list2 != null){ //取较小值的节点 if(list1.val <= list2.val){ cur.next = list1; //只移动取值的指针 list1 = list1.next; }else{ cur.next = list2; //只移动取值的指针 list2 = list2.next; } //指针后移 cur = cur.next; } //哪个链表还有剩，直接连在后面 if(list1 != null) cur.next = list1; else cur.next = list2; //返回值去掉表头 return head.next; } //划分合并区间函数 ListNode divideMerge(ArrayList lists, int left, int right){ if(left > right) return null; //中间一个的情况 else if(left == right) return lists.get(left); //从中间分成两段，再将合并好的两段合并 int mid = (left + right) / 2; return Merge(divideMerge(lists, left, mid), divideMerge(lists, mid + 1, right)); } public ListNode mergeKLists(ArrayList lists) { //k个链表归并排序 return divideMerge(lists, 0, lists.size() - 1); }}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。