刷了 LeetCode 的链表专题，我发现了一个秘密！

关注

发布于: 2020 年 11 月 04 日

刷了 LeetCode 的链表专题，我发现了一个秘密！

引言

链表是以节点（node）存储的链式存储结构，一个 node 包含一个 data 域（存放数据）和一个 next 域（存放下一个 node 的指针），链表的各个节点不一定是连续的，它可以分为带头结点和不带头结点。头结点仅包含 next 域。

如果不熟悉链表的同学，建议先看看我的一篇文章。在这篇文章中，主要讲解使用链表的小技巧，如何使用这些技巧来解题，深入解析了LeetCode中具有代表性的链表题目，相信我，看了这篇文章，你再也不用担心关于链表的题目了。

1、链表的几个概念讲解

事实上，链表的结构比较简单，阻碍我们理解链表的常常是因为链表的指针、边界问题等，这有时会让我们很烦躁，不要慌，我们下面一一对这下概念解析，相信你看了会有收获。

1.1 链表中的的指针是什么

我们学习 C 语言时，学过指针，它描述的是指向一个内存地址，在 Java 语言中，是不存在指针的，但是我们可以把它理解为引用。

当我们将某个变量（对象）赋值给指针（引用），实际上就是将这个变量（对象）的地址赋值给指针（引用）。

p—>next = q; //表示p节点的后继指针存储了q节点的内存地址。p—>next = p—>next—>next; //表示p节点的后继指针存储了p节点的下下个节点的内存地址。

复制代码

1.1 指针指向哪儿

我们写链表代码时，使用的指针的指来指去，很快就把我们搞糊涂了，在这种情况下很容易发生指针丢失和内存泄漏。我们先普及下这两个概念：

指针丢失：自己定义的指针不知道指到哪里了，没有明确的指向。

内存泄漏：链表中的节点没有确切的指针判断，运行时会抛出空指针异常。

我们以插入节点和删除结点来分析指针丢失和内存泄漏的具体情况

插入节点

在节点 a 和节点 b 之间插入节点 x，b 是 a 的下一节点，p 指针指向节点 a，

p—>next = x;x—>next = p—>next;

复制代码

这样的代码会造成指针丢失和内存泄漏，因为这会导致 x 节点的后继指针指向了自己本身。

正确代码应该为：

x—>next = p—>next;p—>next = x;

复制代码

删除节点

同样的，在节点 a 和节点 c 之间删除节点 b，b 是 a 的下一节点，p 指针指向节点 a，正确的代码应该为：

p—>next = p—>next—>next;

复制代码

在删除节点，考虑到删除的节点可能是链表中的第一个节点，我们通常在链表头部加入哨兵(头结点)，这样可以使得删除链表的代码是一致的，不用再额外考虑是否是第一个节点的情况。

在链表加入哨兵的代码为：

 //定义一个哨兵作为传入链表的头结点 ListNode pre =new ListNode(0); pre.next=head;

复制代码

1.3 判断边界的条件

处理链表问题时，要充分考虑链表的边界判断条件，通常情况下，我们经常使用以下几种判断条件：

如果链表为空时，代码是否能正常工作？

如果链表只包含一个结点时，代码是否能正常工作？

如果链表只包含两个结点时，代码是否能正常工作？

代码逻辑在处理头结点和尾结点的时候，是否能正常工作？

这些判断条件需要结合自己的实际场景来使用

2、必须掌握的几类题目

在上面的学习中，我们对链表的一些易错的概念进行了解析，下面，我们就真正的代码实践，我在 LeetCode 上刷题时发现，链表题目通常分为以下几类：

单链表的反转(LeetCode206)
链表中环的检测(LeetCode141)
两个有序链表的合并(LeetCode21)
删除链表(LeetCode18)
删除链表倒数第 n 个结点(LeetCode19)
求链表的中间结点(LeetCode876)

这几类链表题基本涵盖了大部分知识点，在下面的学习中，我们将一一攻克它，相信掌握它们之后，在以后笔试/面试中，更能随心所欲。

2.1 单链表反转(LeetCode206)

思路：从前往后将每个节点的指针反向，即.next 内的地址换成前一个节点的，但为了防止后面链表的丢失，在每次换之前需要先创建个指针指向下一个节点。

class Solution {    public ListNode reverseList(ListNode head) {
if(head==null||head.next==null){return head;}    ListNode p1=head;      //用一个新的链表    ListNode p2=null;    while(p1!=null){        //每次更换指向之前都需要保存下一个节点        ListNode temp=p1.next;        p1.next=p2;        p2=p1;        p1=temp;    }    return p2;    }}

复制代码

2.2 链表中环的检测(LeetCode141)

思路：定义两个指针，p1 和 p2，指针 p1 每次走一步，指针 p2 每次走两步，如果链表中存在环，则必然会在某个时刻满足 p1==p2

public class Solution {    public boolean hasCycle(ListNode head) {        if(head==null||head.next==null){            return false;        }        ListNode slow=head;        ListNode fast=head.next;       while(fast!=null&&fast.next!=null){            if(slow==fast){                return true;            }            slow=slow.next;            fast=fast.next.next;        }        return false;    }}

复制代码

NOTE：对于快指针来说，因为一次跳两步，如果要使用快指针作为判断条件，fast 和 fast.next 都需要判断是否为空。(不可跨级）

2.3 两个有序的链表合并(LeetCode21)

思路：可以新创建一个链表用于合并后的结果，合并的条件如下

两个链表都不为空

>定义一个指针，查找合适的节点并放入新创建链表的下一位置

有一个链表为空

>将不为空的链表放入新创建链表的下一位置

class Solution {    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1==null){            return l2;        }        if(l2==null){            return l1;        }        ListNode result=new ListNode(0);        ListNode temp=result;        //两个链表都不为空        while(l1!=null&&l2!=null){            if(l1.val<=l2.val){                temp.next=l1;                temp=temp.next;                l1=l1.next;            }            else{                temp.next=l2;                temp=temp.next;                l2=l2.next;            }        } //有一个链表为空       if(l1==null){           temp.next=l2;       }       else{           temp.next=l1;       }
        return result.next;    }}

复制代码

2.4 删除链表(LeetCode18)

思路：可以在链表头加一个哨兵(头结点)，删除链表时先找到删除链表的上一个位置，按照删除规则删除即可。

class Solution {    public ListNode deleteNode(ListNode head, int val) {        if(head==null){            return null;        }        //定义一个哨兵作为传入链表的头结点        ListNode pre =new ListNode(0);        pre.next=head;                ListNode temp=pre;        while(temp!=null){            if(temp.next.val==val){                temp.next=temp.next.next;                break;            }            else{                temp=temp.next;            }        }        return pre.next;    }}

复制代码

2.5 删除链表倒数第 n 个结点(LeetCode19)

思路：删除节点时要利用好哨兵(带头结点的链表)

>* 遍历数组的长度 count

>* 找到要删除节点的前一个位置 count-n-1

>* 删除节点

class Solution {    public ListNode removeNthFromEnd(ListNode head, int n) {        ListNode pre=new ListNode(0);        pre.next=head;        ListNode temp1=pre;        ListNode temp2=pre;        int count=0;        while(temp1!=null){            temp1=temp1.next;            count++;        }
        while(count-n-1>0){            temp2=temp2.next;            count--;        }        temp2.next=temp2.next.next;                return pre.next;    }}

复制代码

2.6 求链表的中间结点(LeetCode876)

思路：找出链表中结点的个数 count，然后 count/2 找出中间结点，删除即可。

class Solution {    public ListNode middleNode(ListNode head) {        if(head==null) return null;        ListNode temp=head;       int count=0;       while(temp!=null){        temp=temp.next;        count++;       }       int mid=count/2;       ListNode result=head;       while(mid>0){          result=result.next;          mid--;       }       return result;    }}

复制代码

Note:实践是检验真理的唯一标准，要真正的学好链表这个知识点，仅仅学理论是不可靠的，我们需要多敲代码，多思考，多写多练，针对抽象的题目，可以举例画图，来辅助的自己的思考。

3、学习链表的体会

1、函数中需要移动链表时，最好新建一个指针来移动，以免更改原始指针位置。

2、单链表有带头节点和不带头结点的链表之分，一般做题默认头结点是有值的。

3、链表的内存时不连续的，一个节点占一块内存，每块内存中有一块位置（next）存放下一节点的地址。

3、链表中找环的思想：快慢指针，创建两个指针，一个快指针：一次走两步，一个慢指针：一次走一步，若相遇则有环，若指向 null 则无环。

4、链表找倒数第k个节点思想：创建两个指针，第一个指针查询链表中结点的个数count，然后count-k确定删除结点的位置，用第二个指针遍历链表到count-n-1个位置。

5、反向链表思想：从前往后将每个节点的指针反向，即next内的地址换成前一个节点的，但为了防止后面链表的丢失，在每次换之前需要先创建个指针指向下一个节点。

总结

无论学习任何一个知识点，我们都需要在掌握术(使用方法)的基础上，学习道(本源)，学习数据结构与算法也是一样，我们不仅要掌握如何使用它，更要掌握为什么要是用它，相比其它的方法，它有什么优点，难道是时间复杂度低，空间复杂度小，还是它的数据结构适合这个场景等等...

参考文献

[1]王争.数据结构与算法之美

[2]LeetCode 中国网站

刷题组合拳推荐

笔者在过去的 3 个月时间里整理常用的数据结构与算法和秒杀剑指offer，公众号分别回复数据结构与算法，秒杀剑指offer，即可领取两套电子书，希望能够帮助大家。

我是Simon郎，一个想要每天博学一点点的小青年，关注我，让我们一起进阶，一起博学。

发布于: 2020 年 11 月 04 日阅读数: 1317

原文链接:【http://xie.infoq.cn/article/380dad21eb1ac00eb1941564c】。

Simon郎

关注

自学；制学；博学 2019.10.09 加入

公众号：小郎码知答

发布

暂无评论

创作场景

刷了 LeetCode 的链表专题，我发现了一个秘密！

刷了 LeetCode 的链表专题，我发现了一个秘密！

引言

1、链表的几个概念讲解

1.1 链表中的的指针是什么

1.1 指针指向哪儿

1.3 判断边界的条件

2、必须掌握的几类题目

2.1 单链表反转(LeetCode206)

2.2 链表中环的检测(LeetCode141)

2.3 两个有序的链表合并(LeetCode21)

2.4 删除链表(LeetCode18)

2.5 删除链表倒数第 n 个结点(LeetCode19)

2.6 求链表的中间结点(LeetCode876)

3、学习链表的体会

总结

刷题组合拳推荐

Simon郎

评论