面试必刷TOP101：5、合并k个已排序的链表

一、题目

二、题解

顺序合并解题思路

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; 
    } 
}