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

import java.util.*;
/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */
// 合并k个有序链表，
// 有三种思路，1.逐一合并 时间复杂度为kN 2，递归合并

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param lists ListNode类ArrayList
     * @return ListNode类
     */
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }
        ListNode p = l1, q = l2, m;
        ListNode dummy = new ListNode(0);
        m = dummy;
        while (p != null && q != null) {
            if (p.val <= q.val) {
                m.next = p;
                p = p.next;
                m = m.next;
            } else {
                m.next = q;
                q = q.next;
                m = m.next;
            }
            if (p != null) {
                m.next = p;

            }
            if (q != null) {
                m.next = q;
            }
        }
        System.out.println("Merged List");
        return dummy.next;
    }
    public ArrayList<ListNode> dealList(ArrayList<ListNode> lists) {
        int len = lists.size();
        if (len == 1) {
            return lists;
        }
        ArrayList<ListNode> list1 = new ArrayList<>();
        //偶数  012345
        int i;
        for (i = 0; i + 1 < len; i = i + 2) {
            list1.add(mergeTwoLists(lists.get(i), lists.get(i + 1)));
        }
        if (i + 1 == len) {
            list1.add(lists.get(i));
        }
        return list1;
    }
    public ListNode mergeKLists (ArrayList<ListNode> lists) {
        // write code here
           if (lists == null || lists.size() == 0) {
            return null;
        }
        ArrayList<ListNode> newLists = dealList(lists);

        if (newLists.size() == 1) {
            System.out.println("Merged List长度为1");
            return newLists.get(0);
        }
        return mergeKLists(newLists);

    }
}

利用递归合并的的思路将k个链表合并还可以使用小顶堆。