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

package com.hhdd;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 合并 k 个升序的链表并将结果作为一个升序的链表返回其头节点。
 *
 * @Author huanghedidi
 * @Date 2022/7/23 0:17
 */
public class 合并k个已排序的链表 {


    public static void main(String[] args) {
        ListNode list1 = new ListNode(1).setNext(2);
        ListNode list2 = new ListNode(1).setNext(4).setNext(5);
        ListNode list3 = new ListNode(6);
        ListNode res = mergeKLists2(Arrays.asList(list1, list2, list3));
        ListNode.print(res);
    }

    /**
     * 此解法报超时
     *
     * @param lists
     * @return
     */
    public static ListNode mergeKLists(List<ListNode> lists) {
        if (lists.size() == 0) {
            return null;
        }
        if (lists.size() == 1) {
            return lists.get(0);
        }
        // 使用虚拟头节点简化操作
        ListNode headPre = new ListNode(0);
        ListNode cur = headPre;
        // 设置一个结束标识
        boolean endFlag = false;
        while (true) {
            endFlag = true;
            ListNode minTmpNode = lists.get(0);
            int index = 0;
            for (int i = 0; i < lists.size(); i++) {
                ListNode node = lists.get(i);
                if (node != null) {
                    endFlag = false;
                    if (minTmpNode == null || node.val < minTmpNode.val) {
                        minTmpNode = node;
                        index = i;
                    }
                }
            }
            if (endFlag) {
                break;
            }
            lists.set(index, lists.get(index).next);
            cur.next = minTmpNode;
            cur = cur.next;
        }
        return headPre.next;
    }

    /**
     * 使用类似归并排序的思想解决此问题
     *
     * @param lists
     * @return
     */
    public static ListNode mergeKLists2(List<ListNode> lists) {

        if (lists.size() == 0) {
            return null;
        }
        if (lists.size() == 1) {
            return lists.get(0);
        }
        while (lists.size() >= 2) {
            List<ListNode> newLists = new ArrayList<>();
            for (int i = 0; i < lists.size(); i += 2) {
                // 两两合并
                ListNode cur1 = lists.get(i);
                if (i + 1 < lists.size()) {
                    ListNode cur2 = lists.get(i + 1);
                    newLists.add(mergeTwoSortedList(cur1, cur2));
                } else {
                    newLists.add(mergeTwoSortedList(cur1, null));
                }
            }
            lists = newLists;
        }
        return lists.get(0);
    }

    public static ListNode mergeTwoSortedList(ListNode list1, ListNode list2) {
        if (list1 == null || list2 == null) {
            return list1 == null ? list2 : list1;
        }
        ListNode virtualHead = new ListNode(0);
        ListNode tmp = virtualHead;
        while (list1 != null && list2 != null) {
            if (list1.val < list2.val) {
                tmp.next = list1;
                tmp = tmp.next;
                list1 = list1.next;
            } else {
                tmp.next = list2;
                tmp = tmp.next;
                list2 = list2.next;
            }
        }
        if (list1 == null) {
            tmp.next = list2;
        }
        if (list2 == null) {
            tmp.next = list1;
        }

        return virtualHead.next;
    }

}