Merge

• 例如交替merge，引入index

 public void merge(ListNode left, ListNode right) {
        ListNode dummy = new ListNode(0);
        int index = 0;

        while (left != null && right != null) {
            if (index % 2 == 0) {
                dummy.next = left;
                left = left.next;
            } else {
                dummy.next = right;
                right = right.next;
            }
            dummy = dummy.next;
            index++;
        }

        //check the remaining list
        if (left != null) dummy.next = left;
        else dummy.next = right;
    }

Merged K Sorted List

• Heap, 把所有点都加入到heap中，然后再构建成一个新的LL，需要dummy node
• Divide and Conquer，不断分成左右两部分进行merge。构建的时候需要两个helper，一个是递归的helper来不断分割，另一个是merge两个list

 public ListNode mergeKLists(ListNode[] lists) {

        if (lists == null || lists.length == 0) return null;

        PriorityQueue<ListNode> heap = new PriorityQueue<>(new Comparator<ListNode>() {
            public int compare(ListNode n1, ListNode n2) {
                return n1.val - n2.val;
            }
        });

        ListNode dummy = new ListNode(0);
        ListNode head = dummy;

        for (ListNode node : lists) {
            if (node != null)
                heap.add(node);
        }

        while (!heap.isEmpty()) {
            ListNode node = heap.poll();
            head.next = node;
            head = head.next;
            if (node.next != null)
                heap.add(node.next);
        }
        return dummy.next;
    }