题解 | #牛群的合并#

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param lists ListNode类一维数组
     * @return ListNode类
     */
    public ListNode mergeKLists (ListNode[] lists) {
        // write code here
        if(lists.length==0){
            return null;
        }
        int start = 0;
        int end = lists.length-1;
        return mergeListNode(start, end, lists);
    }

    public ListNode mergeListNode(int start, int end, ListNode[] lists) {
        if (start == end) {
            return lists[start];
        }
        if (end == start + 1) {
            return mergeList(lists[start], lists[end]);
        }
        int mid = (start + end) / 2;
        ListNode listNode1 = mergeListNode(start, mid, lists);
        ListNode listNode2 = mergeListNode(mid + 1, end, lists);
        return mergeList(listNode1, listNode2);
    }


    public ListNode mergeList(ListNode listNode1, ListNode listNode2) {
        ListNode head = new ListNode(0);
        ListNode result = head;
        while (listNode1 != null && listNode2 != null) {
            if (listNode1.val > listNode2.val) {
                head.next = listNode2;
                head = listNode2;
                listNode2 = listNode2.next;
            } else {
                head.next = listNode1;
                head = listNode1;
                listNode1 = listNode1.next;
            }
        }
        if (listNode2 != null) {
            head.next = listNode2;
        }
        if (listNode1 != null) {
            head.next = listNode1;
        }
        return result.next;
    }
}

本题主要考察的知识点为链表的合并，二分合并，所用编程语言为java.

链表的合并和数组的合并算法其实是一样，只不过是两者的数据结构不一样，一个是链表，一个是数组。链表的合并注意点主要是每个链表都是有序的，都是从小到大排列的。

二分合并主要是为了加快合并速度，其实一个一个的进行合并也行不过速度太慢，采用二分合并速度将大大加快