算法（附思维导图+全部解法）300题（23）合并K个升序链表

零标题：算法（leetode，附思维导图 + 全部解法）300题之（23）合并K个升序链表

导读：

项目&作者

1 GitHub - LeetCode项目仓库

0）本项目地址： https://github.com/CYBYOB/algorithm-leetcode 。
目标、愿景：
让每个人都能拥有一定的算法能力、以应对面试中（会举一反三的同学还可以将其融入自己的肌肉和血液，甚至能够赋能于公司的业务和技术）的算法。

1）项目的根目录下的 README.md 文件，
可以帮您快速查阅每1道题的来源、难度、所有的题解方案等。

2）而每个题解（即 index.md 文件）中，
还将附带题目描述、所有的题解方案的思维导图（ .xmind 文件）、思路和技巧等。

3）每种题解方案都有详细的注释，
通过“数字步骤”将抽象的算法逻辑、
清晰和有层次的展示于您的面前。
可以说是，
开箱即用~

4）所有的题解方案都是经过作者1人之手，
故代码风格及其统一。
一旦阅读达到一定量后，
后续将大大提升您的阅读速度 —— “正所谓、量变引起质变”。

5）本人每周仍在不断的更新 —— 保证每周都有新的题目、题解方案刺激着您的神经 和 刷题欲望。
欢迎对算法感兴趣的同学加入我们的社群。
QQ群： 933919972 ；
作者QQ： 1520112971 ；
作者VX： c13227839870（可拉您进群、一起学习与交流~） 。

algorithm-leetcode - 题目总览

2 作者标签

1）“伪全栈工程师，主攻前端，偶尔写点后端”。

2）2019年的微信小程序应用开发赛 - 全国三等奖；
2019CODA比赛 - 前 17/211 强 且 荣获“优秀团队”称号 等。

3）“半自媒体人”，
在校期间、个人公众号（IT三少。新自媒体（公众号）号： 码农三少 ）
在半年内实现了0到5.8K+的粉丝增长等。

一题目描述

题目描述

二解法总览（思维导图）

三全部解法

1 方案1

1)代码：

// 方案1 “化归思想” —— “不熟悉的 --> 熟悉的”。
// 技巧：若 我们并不知道从 A-->C 的最佳路线、但知道 B-->C 的路线，
// 则 原先的 A-->C 问题就变成了 A-->B 问题。
// 步骤：
// 1）初始化变量。
// 2）遍历所有链表，并将每个节点上的值 存入 数组 resArr 里。
// 3）重排 resArr ，使其变得有序。
// 4）遍历 resArr ，将每个元素存在新链表里。
// 5）返回新链表的头结点。
var mergeKLists = function(lists) {
    // 1）初始化变量。
    const l = lists.length;
    let resArr = [];

    // 2）遍历所有链表，并将每个节点上的值 存入 数组 resArr 里。
    for (let i = 0; i < l; i++) {
        let tempHead = lists[i];
        // 2.1）取得每一个链表，不断将它们往后拉 并 存节点值 至 resArr 。
        while (tempHead) {
            resArr.push(tempHead.val);
            tempHead = tempHead.next;
        }
    }

    // 3）重排 resArr ，使其变得有序。
    resArr = resArr.sort((a, b) => a - b);

    // 4）遍历 resArr ，将每个元素存在新链表里。
    const resArrLength = resArr.length;
    let index = 1,
        resHead = tempHead = new ListNode(resArr[0]);

    // 边界：若 lists 为[]、[[]] 时，则直接 return null 即可。
    if (resArrLength === 0) {
        return null;
    }
    // 4.1）遍历 resArr ，将当前元素放入 节点 并 往后拉链表。
    while (index < resArrLength) {
        tempHead.next = new ListNode(resArr[index]);
        tempHead = tempHead.next;
        index++;
    }

    // 5）返回新链表的头结点。
    return resHead;
};

2 方案2

1)代码：

// 方案2 “升级版的化归法”。
// 我们之前写过合并2个有序链表。
// 1）处理边界（其实可以省略，因为核心处理能覆盖）。如 [] 、 [[]] 或 [[1,4,5]] 等。
// 2）核心处理：不断遍历 lists ，每次取其中的2项（l1、l2）、调用 mergeTwoLists 不断将 l1、l2 合并。
// 3）返回结果 resHead（头结点） 。
var mergeKLists = function(lists) {
    // 合并2个有序链表（使用递归）。
    const mergeTwoLists = (l1, l2) => {
        // 1）递归出口。
        if (l1 === null) {
            return l2;
        }
        if (l2 === null) {
            return l1;
        }

        // 2）递归主体。
        // 核心：此时 l1、l2 均不为null。
        const val_1 = l1.val,
            val_2 = l2.val;

        if (val_1 <= val_2) {
            // 2.1）核心：“谁小就需要自己去主动找到自己的下家（即下一个节点 next 值）”。
            l1.next = mergeTwoLists(l1.next, l2);
            // 并将当前小的的节点返回出去 —— 供上层调用 mergeTwoLists 的调用者使用。
            return l1;
        } else {
            // 2.2）核心：“谁小就需要自己去主动找到自己的下家（即下一个节点 next 值）”。
            l2.next = mergeTwoLists(l2.next, l1);
            // 并将当前小的的节点返回出去 —— 供上层调用 mergeTwoLists 的调用者使用。
            return l2;
        }
    }

    const l = lists.length;

    // 1）边界。
    if (l === 0) {
        return null;
    }
    if (l === 1) {
        return lists[0];
    }

    // 2）核心处理：不断遍历 lists ，每次取其中的2项（l1、l2）、调用 mergeTwoLists 不断将 l1、l2 合并。
    // 技巧：数组的“多 变 一” —— 优先考虑 reduce（或 reduceRight） 函数。
    const resHead = lists.reduce((acc, cur) => {
        acc = mergeTwoLists(acc, cur);
        return acc;
    }, null);

    // 3）返回结果 resHead（头结点） 。
    return resHead;
}

3 方案3

1)代码：

// 方案3 ”N指针法“。通过 24 / 133 ，TODO：写法有问题，待完善~
// 注：此时， N = K 。 
var mergeKLists = function(lists) {
    // 获取下一个节点（即 tempHeadList 里最小值对应的节点）。
    const getNextNodeByTempHeadList = (tempHeadList) => {
        // 边界：当前位于“头结点”为null时，不参与“比较”过程。
        tempHeadList = tempHeadList.filter(item => item !== null);

        // 1）找出目前最小值对应的下标
        const l = tempHeadList.length;
        let index = 0,
            resMinIndex = -1,
            resMinVal = Number.POSITIVE_INFINITY;

        while (index < l) {
            const tempVal = tempHeadList[index].val;
            if (tempVal <= resMinVal) {
                resMinVal = tempVal;
                resMinIndex = index;
            }
            index++;
        }

        // 边界：目前最小值对应的下标 为 -1时。
        if (resMinIndex === -1) {
            return [null, []];
        }
        const tempHeadNew = tempHeadList[resMinIndex];
        tempHeadList[resMinIndex] = tempHeadList[resMinIndex].next;

        // 2）返回下一个节点（tempHeadNew） 和 新的tempHeadList。
        return [tempHeadNew, tempHeadList];
    }


    const l = lists.length;
    let tempHeadList = [];

    // 1）遍历 lists ，将每一组的“头结点（非 null 时）”放入 tempHeadList 中，
    // tempHeadList 作为 获取下一个节点（即 tempHeadList 里最小值对应的节点）
    // —— getNextNodeByTempHeadList的输入参数。
    for (let i = 0; i < l; i++) {
        if (lists[i] !== null) {
            tempHeadList.push(lists[i]);
        }   
    }

    let resHead = null,
        tempHead = null;
    while (tempHeadList.length !== 0) {
        const [tempHeadNew, tempHeadListNew] = getNextNodeByTempHeadList(tempHeadList);
        // 边界
        if (tempHeadNew === null) {
            break;
        }

        if (resHead === null) {
            resHead = tempHead = tempHeadNew;
        } else {
            tempHead = tempHeadNew;
        }

        tempHead = tempHead.next;
        tempHeadList = tempHeadListNew;
    }

    // 2）返回结果
    return resHead;
}

4 方案4

1)代码：

class Solution {
    public ListNode mergeKLists(ListNode[] lists) { 
        int k = lists.length;
        ListNode dummyHead = new ListNode(0);
        ListNode tail = dummyHead;
        while (true) {
            ListNode minNode = null;
            int minPointer = -1;
            for (int i = 0; i < k; i++) {
                if (lists[i] == null) {
                    continue;
                }
                if (minNode == null || lists[i].val < minNode.val) {
                    minNode = lists[i];
                    minPointer = i;
                }
            }
            if (minPointer == -1) {
                break;
            }
            tail.next = minNode;
            tail = tail.next;
            lists[minPointer] = lists[minPointer].next;
        }
        return dummyHead.next;
    }
}

参考：
1）https://leetcode-cn.com/problems/merge-k-sorted-lists/solution/4-chong-fang-fa-xiang-jie-bi-xu-miao-dong-by-sweet/

四内推&更多

1 内推

本人是百度的1名工程师，欢迎校招、社招同学向本人投递简历。
本人可内推公司（也可帮忙内推阿里、腾讯、字节、美团、滴滴、京东等）的所有岗位，欢迎私信。

2 更多

以下是个人整理的一些笔记和书籍（永久有效链接: https://pan.baidu.com/s/1SPc3umO6cZlBtoPylSaHzw 密码: eqee ，若失效的话可私信本人或向VX公众号 “码农三少” 发送 “资料” 以进行最新资料的获取）：

理财书籍pdf
技术书籍pdf
个人基金