这十几个链表题型面试必考（详细解析）

如果你和小鹿一样，刚开始对链表的操作代码实现很懵的话，不妨按照小鹿经过一个月的时间对链表相关操作以及题型的整理总结，由浅入深进行适当的练习，我相信，当你真正的练习完这些题目，不但会让你放下对链表心理上的困惑，而且对你学习其他数据结构有很大的信心和帮助！

1、学习建议

小鹿不建议你一口气去看完这篇所有的题目和练习，给自己制定一个小计划，我当初整理该题目的时候，每天都计划认真整理一到题目，把每道题分析透，这样才能达到最好的吸收效果。

2、学习路径

本篇分为三个阶段，基础练习阶段、进阶练习阶段、加强练习阶段。

1）基础练习阶段

首先进行第一个阶段之前，你已经对链表的基础知识能够熟练掌握，但是对于没有动手写过链表代码，那么你从第一阶段最基础的开始进行。确保每一个基础点要亲自动手用自己熟悉的语言写出来，虽然本篇中基本都是 javascript 代码实现的，但是算法思路是一成不变的，如果遇到困难可以自行百度或谷歌，也可以下方给我进行留言。

2）进阶练习阶段

如果你对上述的链表基本代码已经完全熟练掌握了，那么恭喜你可以进行下一个阶段，进阶阶段，这一阶段增加的难度就是链表的操作是对于实际问题来解决的，所以非常锻炼你对问题的分析能力和解决能力，也考验你对代码的全面性、鲁棒性。这一阶段非常的重要，下面的每道题我都做出了详细的分析。

3）加强练习阶段

如果上述的进阶练习阶段的题型你都了如指掌了，那么不妨我们实战一下，LeetCode 汇聚了很多面试的题型，所以我在上边整理了几个经典的题目，你可以尝试着解答它们，相关题目的代码以及解题思路我都整理好了。这一阶段的题目小鹿会在后期不断的更新，这些题目你能够完全掌握，链表对你来说小菜一碟了。

一、链表基础练习（阶段一）

自己首相尝试着一个个攻破下方的链表中最基础的操作，相关代码我也整理好了（先自己尝试着去解决哦）。

• 单链表的插入、删除、查找操作（ 点击查看代码实现 ）。

• 循环链表的插入、删除、查找操作 ( 点击查看代码实现 )。

• 双向链表的插入、删除、查找操作 ( 点击查看代码实现 )。

二、链表进阶练习（阶段二）

1、单链表从尾到头打印

题目：输入一个链表的头结点，从尾到头反过来打印出每个节点的值。

1.1 问题分析与解决

▉ 问题分析

1）看到题目第一想到的就是反转链表在打印输出，一种反转链表的方法，但是这种方法改变了原有的链表结构。

缺点：使得链表的结构发生改变了。如果不改变链表结构应该怎么解决？

2）从问题中可以得出，我们想要从尾到头打印链表，正常情况下是从头到尾打印的，我们就会想到最后的数据先打印，开始的数据最后打印，有种“先进后出”的特点，我们就能想到用“栈”这种结构，用栈来实现。

缺点：代码不够简洁。

优点：鲁棒性好（在不确定的情况下，程序仍然可以正确的执行）。

3）提到栈这种数据结构，我们就会想到“递归”的实现就是用栈这种数据结构实现的。既然栈能实现，那么递归也能实现。

缺点：如果链表很长，递归深度很深，导致堆栈溢出。

优点：代码简洁、明了。

▉ 算法思路

得出以下几种实现方式：

• 反转链表法
• 栈实现
• 递归实现

1）反转链表实现：

从尾到头输出链表的内容，一般的思路就是将链表反转过来，然后从头到尾输出数据。

2）栈实现

从头到尾遍历单链表，将数据存储按照顺序存储到栈中。然后遍历整个栈，打印输出数据。

2）递归实现：

可以通过递归的方式来实现单链表从尾到头依次输出，递归过程涉及到“递”和“归”，反转链表输出数据，正式利用了循环“递”的过程，所以数据先从头部输出，那么递归采用的是“归”的过程来输出内容，输出当前结点先要输出当前节点的下一节点。

▉ 测试用例

在写代码之前，要想好测试用例才能写出健全、鲁棒性的代码，也是为了考虑到边界情况，往往也是整个程序最致命的地方，如果考虑不全面，就会出现 bug，导致程序崩溃。

测试用例：

1）输入空链表；

2）输入的链表只有一个结点；

3）输入的链表有多个结点。

▉ 代码实现：反转链表法

//定义结点
class Node{
    constructor(data){
        this.data = data;
        this.next = null;
    }
}
//定义链表
class LinkedList{
    constructor(){
        this.head = new Node('head');
    }
    
    // 功能：单链表反转
    // 步骤:
    // 1、定义三个指针(pre=null/next/current)
    // 2、判断链表是否可反转(头节点是否为空、是否有第二个结点)
    // 3、尾指针指向第一个结点的 next
    // 4、尾指针向前移动
    // 5、当前指针(current)向后移动
    // 6、将 head 指向单转好的结点
    reverseList = () =>{
        //声明三个指针
        let current = this.head; //当前指针指向头节点
        let pre = null;//尾指针
        let next;//指向当前指针的下一个指针

        //判断单链表是否符合反转的条件(一个结点以上)？
        if(this.head == null || this.head.next == null) return -1;

        //开始反转
        while(current !== null){
            next = current.next;
            current.next = pre;
            pre = current;
            current = next;
        }
        this.head = pre;
    }
    
    //输出结点
    print = () =>{
        let currentNode = this.head
        //如果结点不为空
        while(currentNode !== null){
            console.log(currentNode.data)
            currentNode = currentNode.next;
        }
    }
}
复制代码

▉ 代码实现：循环栈

//方法三：栈实现
const tailToHeadOutput = (currentNode)=>{
    let stack = [];
    //遍历链表，将数据入栈
    while(currentNode !== null){
        stack.push(currentNode.data);
        currentNode = currentNode.next;
    }
    //遍历栈，数据出栈
    while(stack.length !== 0){
        console.log(stack.pop());
    }
}
复制代码

▉ 代码实现：递归

// 步骤:
// 1、判断是否为空链表
// 2、终止条件（下一结点为空）
// 3、递归打印下一结点信息
const tailToHeadOutput = (head)=>{
	// 判断是否空链表
	if(head !== null){
        // 判断下一结点是否为空
	    if(head.next !== null){
            // 下一结点不为空，先输出下一结点
	        tailToHeadOutput(head.next)
	    }
	    console.log(head.data);
	}else{
	    console.log("空链表");
	}
}
复制代码

▉ 性能分析

反转链表实现：

• 时间复杂度：O(n)。需要遍历整个链表，时间复杂度为 O(n)。
• 空间复杂度：O(1)。不需要额外的栈存储空间，空间复杂度为 O(1)。

循环栈实现：

• 时间复杂度：O(n)。需要遍历整个链表，时间复杂度为 O(n)。
• 空间复杂度：O(n)。需要额外的栈存储空间，空间复杂度为 O(n)。

递归实现：

• 时间复杂度：O(n)。需要遍历整个链表，时间复杂度为 O(n)。
• 空间复杂度：O(n)。需要额外的栈存储空间，空间复杂度为 O(n)。

2.2 小结

▉ 考察内容

1）对单链表的基本操作。

2）代码的鲁棒性。

3）循环、递归、栈的灵活运用。

▉ 扩展思考：循环和递归

适用条件：如果需要进行多次计算相同的问题，将采用循环或递归的方式。

递归的优点：代码简洁。

递归的缺点：

1）堆栈溢出：函数调用自身，函数的临时变量是压栈的操作，当函数执行完，栈才清空，如果递归的规模过大，在函数内部一直执行函数的自身调用，临时变量一直压栈，系统栈或虚拟机栈内存小，导致堆栈溢出。

2）重复计算：递归会出现很多的重复计算问题，重复计算对程序的性能有很大影响，导致消耗时间成指数增长，但是可以通过散列表的方式解决。

3）高空间复杂度：递归的每次函数调用都要涉及到在内存开辟空间，压栈、出栈等操作，即耗时又耗费空间，导致递归的效率并不如循环的效率。

扩展：

1）递归—栈：递归的本质是栈，通常用栈循环解决的问题适合于递归。

2）递归-动态规划：动态规划解决问题经常用递归的思路分析问题。关于递归重复计算问题，我们通常使用自下而上的解决思路（动态规划）来解决递归重复计算的问题。

▉ 注意事项：

1）涉及到循环解决的问题，可以想一想能不能使用递归来解决。

2）用递归解决一定要铭记递归的缺点带来的性能问题。

3）递归解决的问题，能不能用动态规划来解决，使得性能更高。

4）用到栈这种数据结构，想一想递归是否可以实现呢。

2、删除链表结点

题目：在 O（1）的时间复杂度内删除链表节点。

给定单向链表的头指针和一个节点指针，定义一个函数在 O（1）时间内删除该节点。

2.1 问题分析与解决

▉ 问题分析

1）想必看到单链表删除节点的题，第一想到的就是删除链表结点需要以 O（n）时间复杂度遍历链表找到该结点的前结点，然后以 O（1）时间复杂度进行删除，时间复杂度为O（n）。而题目中的确实整体要求时间复杂度为 O（1）。

2）怎么才能达到 O（1）的时间复杂度删除链表？如果不遍历不就可以了？如果直接删除的时间复杂度为 O（1），前提是我们需要知道前结点才能做到。我们就会想怎么做到不用遍历数据才能获取到前结点呢？而且必须保证时间复杂度为 O（1）。

3）但是必须让自己多想一步就是如果删除的结点是尾结点怎么操作，如果删除的链表结点只有一个结点，即是尾结点又是头结点怎么办？

▉ 算法思路

得出以下几种实现方式：

• 交换结点法

1）这一有种技巧很难想到，就是我把当前结点的数据与下一结点的数据进行交换，删除下一结点不就可以达到时间复杂度为O（1）了吗。而且我们知道当前结点就是下一结点的前节点，perfect。

2）针对以上两种特殊情况，如果是尾结点，没有下一结点，我们就从头遍历链表删除节点；如果即是尾结点又是头结点，那么删除头结点，并置于 null。

▉ 测试用例

1. 输入空链表；

2）在多个结点链表中删除中间结点；

3）在多个链表中删除头结点；

4）在多个链表总删除尾结点；

5）在只有一个结点链表中删除唯一结点；

▉ 代码实现

// 定义结点
class Node{
    constructor(data){
        this.data = data;
        this.next = null;
    }
}
// 定义链表
class LinkedList{
    constructor(){
        this.head = new Node('head');
    }

    //根据 value 查找结点
    findByValue = (value) =>{
        let currentNode = this.head;
        while(currentNode !== null && currentNode.data !== value){
            currentNode = currentNode.next;
        }
        //判断该结点是否找到
        console.log(currentNode)
        return currentNode === null ? -1 : currentNode;
    }

    //插入元素(指定元素向后插入)
    insert = (value,element) =>{
        //先查找该元素
        let currentNode = this.findByValue(element);
        //如果没有找到
        if(currentNode == -1){
            console.log("未找到插入位置!")
            return;
        }
        let newNode = new Node(value);
        newNode.next = currentNode.next;
        currentNode.next = newNode;
    }

    //遍历所有结点
    print = () =>{
        let currentNode = this.head
        //如果结点不为空
        while(currentNode !== null){
            console.log(currentNode.data)
            currentNode = currentNode.next;
        }
    }

    // 删除节点(核心代码)
    deleteNode = node =>{
        // 判断当前查找的结点是否为 null
        if(node == null) return -1;
        // 1、查找删除的结点
        let d_node = this.findByValue(parseInt(node.data))
        // 2、判断该结点是否为尾结点
        if(d_node.next == null){
            // 重新遍历链表
            let p = null;
            let current = this.head;
            while(current.next !== null){
                p = current;
                current = current.next;
            }
            // 尾结点置为 null
            p.next = null;
        }else{
            // 3、将删除结点的值与下一结点交换
            d_node.data = d_node.next.data;
            // 4、删除下一结点
            d_node.next = d_node.next.next;
        }
    }
}

// 测试 
sortedList1 = new LinkedList()
sortedList1.insert(1, 'head')
sortedList1.insert(2, 1)
sortedList1.insert(3, 2)
sortedList1.insert(4, 3)
sortedList1.print();
console.log('------------------------------删除指定结点----------------------------')
let dnode = new Node('1')
sortedList1.deleteNode(dnode)
sortedList1.print();
复制代码

▉ 性能分析

• 时间复杂度：O（1）。经过上述的方法，删除一个链表的结点，除了删除一个链表的尾结点之外，其他删除节点的时间复杂度为 O（1），获取删除的结点的前一结点，时间复杂度为 O（1），删除节点的时间复杂度为 O（1）。只有删除尾结点才需要遍历整个链表，但大部分删除节点是 O（1）的。使用分析时间复杂度的一个方法摊还分析，将删除节点的时间复杂度平均分到其他大部分情况下，所以平均时间复杂度为 O（1）。

• 空间复杂度：O（1）。不需要额外的内存空间。

2.2 小结

▉ 内容考察

1）对单链表的删除基本操作。
2）对问题的有创新思维的解决能力：能不能将复杂问题的根源用另一种思维去优化。
3）问题考虑的全面性：考虑到问题出现的各种特殊情况，以及边界问题。

3、链表中的倒数第 K 个结点

题目：输入一个链表，输出该链表中倒数第 K 个节点。为符合大多数人的习惯，从 1 开始计数，即链表的尾结点是倒数第一个节点。

3.1 问题分析与解决

▉ 问题分析

1）看到这个题的第一想法就是从链表头遍历到链表尾部，然后尾部倒数 k 个数，因为是单链表，所以倒数并不能实现，想法行不通。

2）那我们只能将思路转移到头结点开始，怎么才能从头结点开始遍历到倒数第 k 个结点呢？大体我们可以得出至少需要遍历两次链表。

3）上述能不能再优化呢？遍历一次链表就可以完成查找？

▉ 算法思路

得出以下几种实现方式：

• 两次遍历法
• 一次遍历法

前提条件：

1）不要忘记判断单链表是否为环型结构

两次遍历法：

1）有一个规律就是链表的长度 n 减去 k 加 1 就是倒数第 k 个数据。所以需要遍历链表得到链表的长度，然后再遍历两次找到链表的倒数第 k 个数据。整个过程需要遍历两遍链表。

一次遍历法：

1）那我们就用到双指针，第一个指针指向第一个结点，第二个指针指向 k - 1 个结点，同时向前移动，直到第二个节点指向尾结点位置，第一个节点就指向了倒数第 k 结点。遍历一遍链表就完成查找。

▉ 测试用例

1）k 的取值范围（0 < k < n）;输入不在范围内的数据。

2）输入空链表。

3）查找倒数第 k 结点为头结点/尾结点。

▉ 代码实现

// 定义结点
class Node{
    constructor(data){
        this.data = data;
        this.next = null;
    }
}
// 定义链表
class LinkedList{
    constructor(){
        this.head = new Node('head');
    }

    //根据 value 查找结点
    findByValue = (value) =>{
        let currentNode = this.head;
        while(currentNode !== null && currentNode.data !== value){
            currentNode = currentNode.next;
        }
        //判断该结点是否找到
        console.log(currentNode)
        return currentNode === null ? -1 : currentNode;
    }

    //插入元素(指定元素向后插入)
    insert = (value,element) =>{
        //先查找该元素
        let currentNode = this.findByValue(element);
        //如果没有找到
        if(currentNode == -1){
            console.log("未找到插入位置!")
            return;
        }
        let newNode = new Node(value);
        newNode.next = currentNode.next;
        currentNode.next = newNode;
    }

    //遍历所有结点
    print = () =>{
        let currentNode = this.head
        //如果结点不为空
        while(currentNode !== null){
            console.log(currentNode.data)
            currentNode = currentNode.next;
        }
    }

    // 检测单链表是否为环
    checkCircle = ()=>{
        // 判断是否为空链表
        if(this.head == null) return fast;
        // 定义快慢指针
        let fast = this.head.next;
        let low = this.head;
        //进行循环判断(当前 fast 结点/fast 移动两步后的结点是否为 null)
        while(fast !== null && fast.next !== null){
            // fast 指针向前移动两步
            fast = fast.next.next;
            // low 指针向前移动一步
            low = low.next;
            // 如果为环，总有一天会相遇
            if(fast === low) return true;
        } 
        return false;
    }

    // 查找倒数第 k 结点
    findByIndexFromEnd = k =>{
        //判断 k 是否大于0
        if(k < 1) return 'k 的大小不在搜索范围内';
        // 检测是否为环
        if(this.checkCircle()) return false;
        // 定义两个指针进行遍历
        let current = this.head;
        let fast = current;
        let low = current;

        let pos = 0;
        for(let i = 1;i <= k - 1;i++){
            if(fast.next !== null){
                fast = fast.next;
            }else{
                // k 的大小超出链表大小的范围
                return 'k 的大小超出链表的范围';
            }
        }

        // low 和 fast 指针同时移动
        while(fast.next !== null){
            fast = fast.next;
            low = low.next;
        }

        // 返回倒数第 k 结点
        return low;
    }
}
// 测试
const list = new LinkedList();
list.insert('1','head');
// list.insert('2','1');
// list.insert('3','2');
// list.insert('4','3');
// list.insert('5','4');
// list.insert('6','5');
list.print();
console.log('-------------------查找倒数第 k 结点----------------')
console.log(list.findByIndexFromEnd(8)); 
复制代码

▉ 性能分析

两次遍历法：

• 时间复杂度：O（k*n）。当 k 趋近于 n 时，最坏时间复杂度为 O（n^2）。
• 空间复杂度：O（1）。不需要额外的内存空间。

一次遍历法：

• 时间复杂度：O（n）。只需要遍历一次单链表，所以时间复杂度为O（n）。
• 空间复杂度：O（1）。不需要额外的内存空间。

3.2 小结

▉ 内容考察

1）对单链表的基本操作。

2）代码的全面性、鲁棒性。

▉ 注意事项

1）当我们用一个指针不能解决时，想一想两个指针能否解决？

▉ 相关题目

1）求中间结点

2）求倒数第 k 个结点

3）检测环的存在

4、反转链表

题目：定义一个函数，输入一个链表的头结点，反转该链表并输出反转链表的头结点。

4.1 问题分析与解决

▉ 问题分析

反转链表的我们第一能够想到的方法就是最常用的方法，声明三个指针，把头结点变为尾结点，然后下一结点拼接到尾结点的头部，一次类推。说白了就是就是直接将链表指针反转就可以实现反转链表。

▉ 算法思路

1）定义三个指针，分别为 Pnext、pre、current，current 存储当前结点， pre 指向反转好的结点的头结点，Pnext 存储下一结点信息。

2）判断当前结点是否可以反转（是否为空链表或链表大于 1 个结点）?

步骤：

1）Pnext 指针存储下一结点 。

2）当前结点的 next 结点是否为 null (为 null 的话当前结点就是最后的一个结点)，如果为 null，将当前节点赋值为 head 头指针（断裂处）。

3）将 pre 指针指向的结点赋值当前节点 current 的下一结点 next。

4）然后让 pre 指针指向当前节点 current。

5）current 继续遍历, 当前节点指向 current 指向 Pnext。

递归法（重点分析）：

1）先确定终止条件：当下一结点为 null 时，返回当前节点；

2）判断当前的链表是否为 null；

3）递归找到尾结点，将其存储为头结点。

4）此时递归的层次是第二层递归，所以要设置为头结点的下一结点就是当前第二层结点，并且将第二节点的下一结点设置为 bull。

▉ 测试用例

1）链表是空链表。

2）当前链表的长度小于等于 1。

3）输入长度大于 1 的链表。

▉ 代码实现

var reverseList = function(head) {
    // 判断当前链表是否为空链表
    if(head == null) return null;

    // 定义三个指针
    let [current,prev,next] = [head,null,null];

    while(current !== null){
        //1、存储下一结点
        next = current.next;
        if(next == null){
            head = current;
        }
        current.next = prev;
        prev = current;
        current = next;
    }
    return head;
};
复制代码

▉ 递归法

const reverseList = (head)=>{
    //如果链表为空或者链表中只有一个元素
    if(head == null || head.next == null){
        return head;
    }else{
        //先反转后面的链表，走到链表的末端结点
        let newhead = reverseList(head.next);
        //再将当前节点设置为后面节点的后续节点
        head.next.next = head;
        head.next = null;
        return newhead;
    }
}
复制代码

▉ 性能分析

• 时间复杂度：O(n)。只需遍历整个链表就可以完成反转，时间复杂度为 O(n)。
• 空间复杂度：O(1)。只需要常量级的空间，空间复杂度为 O(1)。

4.2 小结

▉ 内容考察

1）对单链表的基本操作。

2）对指针操作顺序的逻辑性考察。

3）考察思维的全面性以及代码的鲁棒性。

▉ 注意事项

1）边界条件。
2）写代码之前想好测试用例，写完代码一一验证测试用例的正确性。

5、合并两个有序链表

题目：输入两个递增 排序 的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。

5.1 问题分析与解决

▉ 问题分析

1）合并两个链表，经常犯的错误就是没有弄清除指针的指向，导致链表合并的时候断裂以及代码全面性考虑的不全，也就是代码的鲁棒性存在问题。

2）递归。每次都要比较两个结点大小，是否可以使用递归来解决呢？

▉ 算法思路

一般解决法：

1）合并两个链表，首先需要两个指针，分别指向两个链表。

2）比较两个指针指向结点元素的大小，小的结点添加到新链表，然后指针向后移动继续比较。

3）直到其中一个链表没有结点了，另一个链表存在结点，将剩余的结点加入到新链表的尾部，完成合并。

递归法：（满足递归的三个条件）

比较当前结点大小先比较下一结点的大小。

1）结点之间的比较可以分的子问题为每个节点的比较。

2）终止条件：其中一个链表结点为 null。

3）子问题和总问题具有相同的解决思路。

▉ 测试用例

1）输入两个空链表。

2）其中一个链表为空链表。

3）输入两个完整的链表。

▉ 代码实现

// 功能:两个有序链表的合并
// 步骤:
// 1、判断两个链表是否为 null,并将链表赋予临时变量
// 2、声明合并链表,通过 currentNode 指向当前结点
// 3、两个链表比较大小,数值小的添加到合并链表中,合并链表进行指针移动
// 4、将链表剩余数据添加到合并链表后边
const mergeSortList = (listA,listB) =>{
    //判断链表是否为空
    if(listA === null) return false;
    if(listB === null) return false;
    let a = listA;
    let b = listB;

    //声明合并链表,通过 currentNode 指向当前结点
    let resultList = undefined

    //两个链表比较大小,数值小的添加到合并链表中,合并链表进行指针移动
    if (a.data < b.data) {
        resultList = a
        a = a.next
    } else {
        resultList = b
        b = b.next
    }
    let currentNode = resultList;
    while (a !== null && b !== null) {
        if (a.data < b.data) {
            currentNode.next = a
            a = a.next
        } else {
            currentNode.next = b
            b = b.next
        }
        currentNode = currentNode.next
    } 

    // 将链表剩余数据添加到合并链表后边 
    if(a !== null){
        currentNode.next = a;
    }else{
        currentNode.next = b;
    }
    //返回合并链表
    return resultList;
}
复制代码

▉ 递归实现

var mergeTwoLists = function(l1, l2) {
    let result = null;
    //终止条件
    if(l1 == null) return l2;
    if(l2 == null) return l1;

    //判断数值大小递归
    if(l1.val < l2.val){
        result = l1;
        result.next = mergeTwoLists(l1.next,l2);
    }else{
        result = l2;
        result.next = mergeTwoLists(l2.next,l1);
    }

    //返回结果
    return result;
};
复制代码

▉ 代码测试

//定义结点
class Node{
    constructor(data){
        this.data = data;
        this.next = null;
    }
}

//定义链表
class LinkedList{
    constructor(){
        this.head = new Node('head');
    }

    //根据 value 查找结点
    findByValue = (value) =>{
        let currentNode = this.head;
        while(currentNode !== null && currentNode.data !== value){
            currentNode = currentNode.next;
        }
        //判断该结点是否找到
        console.log(currentNode)
        return currentNode === null ? -1 : currentNode;
    }

    //插入元素(指定元素向后插入)
    insert = (value,element) =>{
        //先查找该元素
        let currentNode = this.findByValue(element);
        //如果没有找到
        if(currentNode == -1){
            console.log("未找到插入位置!")
            return;
        }
        let newNode = new Node(value);
        newNode.next = currentNode.next;
        currentNode.next = newNode;
    }

    //遍历所有结点
    print = () =>{
        let currentNode = this.head
        //如果结点不为空
        while(currentNode !== null){
            console.log(currentNode.data)
            currentNode = currentNode.next;
        }
    }
}
// 合并两个链表
var mergeSortList = function(l1, l2) {
    let result = null;
    //终止条件
    if(l1 == null) return l2;
    if(l2 == null) return l1;

    //判断数值大小递归
    if(l1.val < l2.val){
        result = l1;
        result.next = mergeSortList(l1.next,l2);
    }else{
        result = l2;
        result.next = mergeSortList(l2.next,l1);
    }

    //返回结果
    return result;
};

// 测试
sortedList1 = new LinkedList()
sortedList1.insert(9, 'head')
sortedList1.insert(8, 'head')
sortedList1.insert(7, 'head')
sortedList1.insert(6, 'head')
sortedList1.print();
sortedList2 = new LinkedList()
sortedList2.insert(21, 'head')
sortedList2.insert(20, 'head')
sortedList2.insert(19, 'head')
sortedList2.insert(18, 'head')
sortedList2.print();
console.log('----------------合并两个有序的链表----------------')
let resultList = mergeSortList(sortedList1.head.next,sortedList2.head.next)
while (resultList !== null) {
    console.log(resultList.date);
    resultList = resultList.next;
}
复制代码

▉ 性能分析

• 时间复杂度：O（n）。n 为较短的链表的长度。
• 空间复杂度：O（n+m）。需要额外的 n+m(两个链表长度之和) 大小的空间来存储合并的结点。

5.2 小结

▉ 内容考察

1）对链表的基本操作。

2）写代码考虑问题的全面性和鲁棒性。

▉ 注意事项

1）递归实现，注意递归解决问题的三个缺点。

• 堆栈溢出
• 重复数据
• 高空间复杂度

三、LeetCode 加强练习阶段（阶段三）

如果你对基本的链表操作已经掌握，想进一步提高对链表熟练度的操作，可以练习一下 LeetCode 题目。每道题我都做了详细的解析，如：问题分析、算法思路、代码实现、考查内容等，有关链表的相关题目会不断更新......

• 环形链表 I ( 题目解析 )
• 环形链表 II ( 题目解析 )
• 合并K个排序链表 ( 题目解析 )

四、链表总结

做了大量有关链表的题型之后，对链表的操作做一个总结和复盘，对链表有一个整体的把握和重新的认识。

1、结构上

1）存储链表的内存空间是不连续的，所有需要使用指针将这些零碎内存空间连接起来，导致需要通过指针来进行操作，这也是为什么链表中大多数都是关于指针的操作的原因。

2）链表在结构上有两个特殊的地方就是链表头和链表尾，很多操作都要对链表头和链表尾进行特殊处理，所以我们可以借助哨兵思想（在链表头添加一个哨兵），这样带头的链表可以简化问题的解决。

2、操作上

1）递归：链表中的很多操作都是可以用递归来进行解决的，因为链表的每个结点都有着相同的结构，再加上解决的问题可以分解为子问题进行解决。所以在链表中递归编程技巧还是非常常用的。如：从尾到头打印链表、合并两个有序链表、反转链表等。

2）双指针：链表中大部分都是进行指针操作，链表属于线性表结构（形如一条线的结构），很多问题可以使用双指针来解决，也是非常常用到的。如：查找倒数第K 结点、求链表的中间结点等。

3、性能上

1）链表正是因为存储空间不连续，对 CPU 缓存不友好，随时访问只能从头遍历链表，时间复杂度为 O（n），但是链表的这种结构也有个好处就是。可以动态的申请内存空间，不需要提前申请。

2）指针的存储是需要额外的内存空间的，如果存储的数据远大于存储指针的内存空间，可以进行忽略。

作者：小鹿

座右铭：追求平淡不平凡，一生追求做一个不甘平凡的码农!

本文首发于 Github ，转载请说明出处。

个人公众号：一个不甘平凡的码农。