合并 k 个有序链表

问题描述

• leetcode 23， Merge k Sorted Lists
  解题思路
  合并2个有序链表的进阶版，很容易想到，利用分治进行处理。
  把个数大于2的集合 两两划分处理，最后再做最后一步的处理。

  public class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists.length==0 || lists==null) { return null; }
        return merge(lists, 0, lists.length-1);
    }
    public static ListNode merge(ListNode[] lists, int left, int right) {
        if (left == right) { return lists[left]; }
        int mid = left + (right-left)/2;
        ListNode l1 = merge(lists, left, mid);
        ListNode l2 = merge(lists, mid+1, right);
        return merger2Lists(l1, l2);
    }
    public static ListNode merger2Lists(ListNode l1, ListNode l2) {
        // 递归写法
        if (l1==null) { return l2; }
        if (l2==null) { return l1; }
        ListNode head = null;
        if (l1.val < l2.val) {
            head = l1;
            head.next = merger2Lists(l1.next, l2);
        } else {
            head = l2;
            head.next = merger2Lists(l1, l2.next);
        }
        return head;
    }
}