题解 | #牛群的合并#

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
        int len = lists.length;
        if (len == 0) return null;
        if (len == 1) return lists[0];
        ListNode head = lists[0];
        for (int i = 1; i < len; i++) {
            head = mergeList(head, lists[i]);
        }
        return head;
    }
    private ListNode mergeList(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;
        ListNode hair = new ListNode(0), p = l1.val < l2.val ? l1 : l2, q = p == l1 ? l2 : l1, next;
        hair.next = p;
        while (p != null && q != null) {
            while (p.next != null && p.next.val < q.val) p = p.next;
            next = p.next;
            p.next = q;
            p = q;
            q = next;
        }
        return hair.next;
    }
}

• 根据题意，对于多组链表的合并，可以分解成两个链表的合并
• 定义两个指针 p、q，分别指向两个链表头节点值的一小、一大
• 每次将较小值的节点接到较大值的节点后面，依次类推。。