题解 | #合并k个已排序的链表#

import java.util.*;

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

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param lists ListNode类ArrayList 
     * @return ListNode类
     */
    public ListNode mergeKLists (ArrayList<ListNode> lists) {
        // write code here
        if(lists == null || lists.size() == 0) return null;
        ListNode first = lists.get(0);
        if(lists.size() == 1) return first;
        ListNode head = null;
        for(int i = 1; i < lists.size(); i++) {
            ListNode h = lists.get(i);
            first = mergreNodes(first, h);
        }
        return first;
    }

    public ListNode mergreNodes(ListNode head1, ListNode head2) {
        if(head1 == null) return head2;
        if(head2 == null) return head1;

        ListNode dummy = new ListNode(-10000);
        ListNode pos = dummy;

        while(head1 != null && head2 != null) {
            if(head1.val <= head2.val) {
                pos.next = head1;
                pos = pos.next;
                head1 = head1.next;
            } else {
                pos.next = head2;
                pos = pos.next;
                head2 = head2.next;
            }
        }

        if(head1 == null) {
            pos.next = head2;
        } else {
            pos.next = head1;
        }

        return dummy.next;
    }
}