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

采用败者树的思想解决本题：

败者树是一棵完全二叉树，所以可以用数组的形式很方便的构建，数组的长度等于链表的个数即可。数组中存储的是链表在集合中的索引位置。

对于完全二叉树和败者树不了解的，需要去找些视频资料学习一下，光靠文字，理解起来可能有点费劲。当然图片弄的好也能达到理解的效果，我就不整这么多了。

虽然按照败者树，时间负责度应该是O(nlogn)，空间负责度是O(1)。但是，执行效率却很慢，不知道为啥~

我觉得这个思想还是ok的。

import java.util.*;
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
/**
 * 合并k个已排序的链表
 */
public class Solution {

    /**
     * 采用败者树的思想，每次选出所有链表中头节点的值最小的节点
     * @param lists 多个已排序链表
     * @return  合并后的新链表
     */
    public ListNode mergeKLists(ArrayList<ListNode> lists) {
        if (lists == null || lists.size() == 0) {
            return null;
        }
        //新链表的头节点
        ListNode newHead = new ListNode(0);
        ListNode node = newHead;
        LoserTree loserTree = new LoserTree(lists);
        while (!loserTree.isEmpty()) {
            node.next = loserTree.poll();
            node = node.next;
        }
        return newHead.next;
    }

}

/**
 * 败者树
 * 关键字小的为胜者
 */
class LoserTree {

    /**
     * 以顺序存储方式保存所有非叶子结点
     */
    Integer[] tree;
    /**
     * 叶子节点的个数
     */
    int size;
    /**
     * 叶子节点
     */
    ArrayList<ListNode> leaves;

    /**
     * 构建败者树
     *
     * @param leaves 叶子节点
     */
    public LoserTree(ArrayList<ListNode> leaves) {
        this.leaves = leaves;
        this.size = leaves.size();
        this.tree = new Integer[size];
        for (int i = 0; i < size; i++) {
            adjust(i);
        }
    }

    /**
     * 当最强者已经成null时表示已经完成了全部排序
     *
     * @return 是否所有的都遍历完毕
     */
    public boolean isEmpty() {
        return leaves.get(tree[0]) == null;
    }

    /**
     * @return 当前最强者
     */
    public ListNode poll() {
        //旧的胜者在集合中的索引位置
        int old = tree[0];
        //旧的胜者节点
        ListNode oldWinner = leaves.get(old);
        //旧的胜者所在的链表指针指向下一个
        leaves.set(old, oldWinner.next);
        //新的挑战者发起挑战：也就是旧胜者所在链表的下一个节点
        adjust(old);
        //返回旧的胜者节点
        return oldWinner;
    }

    /**
     * 从最底层的非叶子节点开始一层一层的向上pk
     * 存在两种情况：
     * 1、要pk的位置为空，直接占据这个位置
     * 2、要pk的位置不为空，跟这个位置的人pk，胜了就往上走，败了就留在这个位置，原来在这个位置的人往上走
     *
     * @param pk 叶子节点在集合中的index
     */
    private void adjust(int pk) {
        //叶子节点的父节点，也是最底层的非叶子节点
        int p = (pk + size) / 2;
        while (p > 0) {
             if (tree[p] == null){
                //首次初始化时，父节点虚位以待，pk者直接放到这里
                tree[p] = pk;
                break;
            }
            if (leaves.get(tree[p]) == null) {
                //如果父节点所指链表已为空，挑战者直接胜利
            }else if (leaves.get(pk) == null || leaves.get(tree[p]).val < leaves.get(pk).val) {
                //更换挑战者
                pk = tree[p] ^ pk;
                tree[p] = tree[p] ^ pk;
                pk = tree[p] ^ pk;
            }
            //挑战下一个
            p = p / 2;
        }
        //最后胜者
        tree[0] = pk;
    }
}