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

public class Solution {
    public ListNode mergeTwoLists(ListNode left, ListNode right) {
        ListNode p = left;
        ListNode q = right;
        ListNode newHead = null;
        ListNode prev = null;

        while (p != null && q != null) {
            ListNode newNode = null;
            if (p.val <= q.val) {
                newNode = new ListNode(p.val);
                p = p.next;
            } else {
                newNode = new ListNode(q.val);
                q = q.next;
            }
            if (newHead == null) {
                newHead = newNode;
            }
            if (prev != null) {
                prev.next = newNode;
            }
            prev = newNode;
        }
        while (p != null) {
            ListNode newNode = new ListNode(p.val);
            if (newHead == null) {
                newHead = newNode;
            }
            if (prev != null) {
                prev.next = newNode;
            }
            prev = newNode;
            p = p.next;

        }
        while (q != null) {
            ListNode newNode = new ListNode(q.val);
            if (newHead == null) {
                newHead = newNode;
            }
            if (prev != null) {
                prev.next = newNode;
            }
            prev = newNode;
            q = q.next;

        }
        return newHead;
    }
    public ListNode mergeKLists (ArrayList<ListNode> lists) {
        // write code here
        int sz = lists.size();
        if (sz == 0) {
            return null;
        }
        if (sz == 1) {
            return lists.get(0);
        }
        if (sz == 2) {
            return mergeTwoLists(lists.get(0), lists.get(1));
        }

        new ArrayList<>(lists.subList(0, sz/2));
        
        return  mergeTwoLists( 
		  		mergeKLists(new ArrayList<>(lists.subList(0, sz/2))), 
         		mergeKLists(new ArrayList<>(lists.subList(sz/2, sz)))
		);
    }
}

采用分治思想，将原链表数组分成左右两部分（看成一个整体），最后利用上一题写的两个链表合并方法递归解决。