题型篇 | 数据结构与算法之链表系列

星光闪亮图书馆 2019-12-21

展开全文

写在前边

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

由于文章篇幅共计 8000 字，公众号为缩减版本，完整版请查看文章底部链接。

学习建议

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

学习路径

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

1、基础练习阶段

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

2、进阶练习阶段

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

3、加强练习阶段

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

阶段一：链表基础练习

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

1、单链表的插入、删除、查找操作（☛题目解析）

2、循环链表的插入、删除、查找操作（☛题目解析）

3、双向链表的插入、删除、查找操作（☛题目解析）

阶段二：链表进阶练习

1、单链表从尾到头打印

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

1.1 问题分析与解决

▉ 问题分析

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

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

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

※缺点：代码不够简洁。

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

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

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

※优点：代码简洁、明了。

▉ 算法思路

通过上边的问题分析，得出以下几种解决方法：

● 反转链表法

● 栈实现

● 递归实现

1、反转链表实现

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

2、栈实现

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

3、递归实现

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

▉ 测试用例

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

1、输入空链表；

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

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

▉ 代码实现

1、代码实现：反转链表法

 1//定义结点
 2class Node{
 3    constructor(data){
 4        this.data = data;
 5        this.next = null;
 6    }
 7}
 8//定义链表
 9class LinkedList{
10    constructor(){
11        this.head = new Node('head');
12    }
13
14    // 功能：单链表反转
15    // 步骤:
16    // 1、定义三个指针(pre=null/next/current)
17    // 2、判断链表是否可反转(头节点是否为空、是否有第二个结点)
18    // 3、尾指针指向第一个结点的 next
19    // 4、尾指针向前移动
20    // 5、当前指针(current)向后移动
21    // 6、将 head 指向单转好的结点
22    reverseList = () =>{
23        //声明三个指针
24        let current = this.head; //当前指针指向头节点
25        let pre = null;//尾指针
26        let next;//指向当前指针的下一个指针
27
28        //判断单链表是否符合反转的条件(一个结点以上)？
29        if(this.head == null || this.head.next == null) return -1;
30
31        //开始反转
32        while(current !== null){
33            next = current.next;
34            current.next = pre;
35            pre = current;
36            current = next;
37        }
38        this.head = pre;
39    }
40
41    //输出结点
42    print = () =>{
43        let currentNode = this.head
44        //如果结点不为空
45        while(currentNode !== null){
46            console.log(currentNode.data)
47            currentNode = currentNode.next;
48        }
49    }
50}

2、代码实现：循环栈

 1//方法三：栈实现
 2const tailToHeadOutput = (currentNode)=>{
 3    let stack = [];
 4    //遍历链表，将数据入栈
 5    while(currentNode !== null){
 6        stack.push(currentNode.data);
 7        currentNode = currentNode.next;
 8    }
 9    //遍历栈，数据出栈
10    while(stack.length !== 0){
11        console.log(stack.pop());
12    }
13}

3、代码实现：递归

 1// 步骤:
 2// 1、判断是否为空链表
 3// 2、终止条件（下一结点为空）
 4// 3、递归打印下一结点信息
 5const tailToHeadOutput = (head)=>{
 6    // 判断是否空链表
 7    if(head !== null){
 8        // 判断下一结点是否为空
 9        if(head.next !== null){
10            // 下一结点不为空，先输出下一结点
11            tailToHeadOutput(head.next)
12        }
13        console.log(head.data);
14    }else{
15        console.log('空链表');
16    }
17}

▉ 性能分析

1、反转链表实现

● 时间复杂度：O(n)。需要遍历整个链表，时间复杂度为 O(n)。

● 空间复杂度：O(1)。不需要额外的栈存储空间，空间复杂度为 O(1)。

2、循环栈实现

● 时间复杂度：O(n)。需要遍历整个链表，时间复杂度为 O(n)。

● 空间复杂度：O(n)。需要额外的栈存储空间，空间复杂度为 O(n)。

3、递归实现

● 时间复杂度：O(n)。需要遍历整个链表，时间复杂度为 O(n)。

● 空间复杂度：O(n)。需要额外的栈存储空间，空间复杂度为 O(n)。

2.2 小结

▉ 考察内容