题解 | 合并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) {
       ListNode head=new ListNode(1);//设置一个头结点,后面结果会挂在这个节点上
        TreeSet<ListNode> ts=new TreeSet<>((o1,o2)-> {
            return o1.val - o2.val==0?1:o1.val - o2.val;
        });//用TreeSet高效实现获取最小节点
        for (int i = 0; i < lists.size(); i++) {
            if(lists.get(i)!=null){
                ts.add(lists.get(i));
            }
        }//将所有头结点添加进ts
        ListNode cur=head;//设置一个结果链表上的指针
        while (ts.size()>0){
            ListNode node=ts.pollFirst();//获取并弹出最小节点
            cur.next=node;
            cur=cur.next;//挂载并移动指针
            if(node.next!=null){
                ts.add(node.next);
            }//将最小节点的下一个节点重新加入ts
        }//循环会持续到所有结点挂载完毕
        return head.next;
    }
}

这道题的关键在于利用原链表的升序性质简化计算,TreeSet可以很好的实现这一点