力扣 24 两两交换链表中的节点

题意：给定一个链表，交换每两个节点的顺序

思路：

1. 新建结果链表
2. 把n个链表的头节点放到一个treeset里边(还可以用priorityqueue)
3. 然后每次取出treeset中最小的头节点加入到结果链表中，如果该节点的下一个节点不为空，把该头节点的下一个节点加到treeset中，直到treeset为空

思想：treeset，注意这里还可以用priorityqueue，二者的区别可见：https://www.jianshu.com/p/2870a1e3f65a

复杂度：时间O（klgk)，空间O(k)，k为链表的个数

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        TreeSet<ListNode> treeSet = new TreeSet(new Comparator<ListNode>(){
            public int compare(ListNode n1, ListNode n2) {
                // treeset 没有hashcode和equals方法，完全依赖Comparator来确定元素是否相等，
               // 因此，下边的方法强制让值相等的不同节点加入到treeset中
                if(n1.val == n2.val)
                    return 1;
                return n1.val - n2.val;
            }
        });
        ListNode newhead = new ListNode(0);
        ListNode runner = newhead;
        for(ListNode node: lists) {
            if(node != null)
                treeSet.add(node);
        }
        while(!treeSet.isEmpty()) {
            runner.next = treeSet.pollFirst();
            runner = runner.next;
            if(runner.next != null) {
                treeSet.add(runner.next);
                runner.next = null;
            }
        }
        
        return newhead.next;
    }
}