一、题目
二、题解
顺序合并解题思路
1、将k个链表配对并将同一对中的链表进行合并（采用顺序合并的方法）
2、第一轮合并后，k个链表合并成了 k/2 个链表，平均长度 2n/k ，然后是 k/4、k/8...等等
3、重复这一过程，知道获取最终的有序链表
import java.util.*;
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode mergeKLists(ArrayListlists) {
// 采用分治进行合并链表
return mergeList( lists , 0 , lists.size() - 1 );
}
// 分治进行链表两两合并
public ListNode mergeList(ArrayListlists , int L ,int R){
if(L == R){
return lists.get(L);
}
if(L > R){
return null;
}
int mid = L + ((R - L) >> 1);
return merge( mergeList(lists,L,mid) , mergeList(lists,mid+1,R));
}
// 合并两个链表，对比合并
public ListNode merge(ListNode l1 , ListNode l2){
if(l1 == null || l2 == null){
return l1 == null ? l2 : l1;
}
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;
}
cur.next = (l1 == null ? l2 : l1); return dummy.next;
}
}