关于链表的一二三事

前言

相信大家对于链表已经是很了解了，那么接下来让我从头开始一 一道来（如果还不是很熟悉的小伙伴还不赶紧上车😏)

本文将从下面几个点来讲解链表：

什么是链表

链表的定义

链表（Linked List）是一种在物理上非连续、非顺序的数据结构，是一种线性表，由若干个节点(node)所组成

而链表又分为单向链表和双向链表

当然不仅仅只有这两种链表，还遇到过一种链表节点有一指针random指向其他的节点，但大体上链表节点都是一存储数值的val加上指向其他节点的指针

单向链表的每一个节点包含两部分，一部分是存放数据的变量val，以及指向下一个节点的指针next

值得注意的是，链表的第一个节点被称为头节点，最后一个节点被称为尾节点，而尾节点的next指针是指向null的，也即是空指针

由此可以简单写出单向链表节点的定义：

public class ListNode {	int val;	ListNode next;	ListNode(int x) { val = x; }}

既然单向链表的节点是指向下一个节点的，那么双向链表的节点就还可以指向上一个节点，是不是很合理😃

双向链表对比单向链表多了一个访问上一个节点的prev指针

相信到这里朋友们应该能想到双向链表节点是怎么定义的，这里就不展开了😜

作为一种常见的基础数据结构，链表很多时候都会被用到，就比如B+树在同一层级中的页与页之间排成了一个双向链表，而单个页内的记录则是排成了一个单向链表

哑节点

哑节点(dummy node)，也被称为哨兵节点，其实就是一个虚拟节点作为头节点，至于这个节点里存储了什么不是很重要，它本身也是为了方便而引入的

哑节点作为第一个节点，可以避免处理头节点为空的边界条件，换句话说，它可以省略当函数的入口参数为空时的判断，比如这个使用了哑节点的链表定义：

class LinkedList {    int length = 0; // 链表长度，非必须    ListNode head = new ListNode(0); // 哑节点        public void addNode(int val) {        ListNode tmp = head;        while (tmp != null) {            tmp = tmp.next;        }        tmp.next = new ListNode(val);        length++;    }}

链表的存储方式

大家应该知道数组在内存中的存储方式是 顺序存储，那么，不同于数组，链表的在内存中的存储方式为随机存储

内存是由一个个连续的内存单元所组成的，每一个内存单元都有自己的地址，在这些内存单元中，有些被其他数据占用了，有些则是空闲的

就比如上图数组中，灰色即代表被占用存储单元，绿色即代表空闲的存储单元，而红色即是数组在内存中的位置

可以发现，数组中的每一个元素，都存储在对应的内存单元中，并且元素之间排列紧密，既不能打乱元素的存储顺序，也不能跳过某个存储单元进行存储，这也就是数组的顺序存储

相对的，链表的每一个节点可以分布在内存的不同位置，节点之间依靠next指针关联起来，这样就可以很好的利用内存中零散的碎片空间，也即是链表的随机存储

链表的基本操作

链表节点的查找

不同于数组可以直接通过下标来快速定位数组元素，链表只能从头节点往后逐一查找

就比如要查找给定链表的从头开始的第三个节点：

• 首先需要定义一个指针指向链表的头节点，之后依靠链表节点的next往后遍历查找

• 当找到链表从头开始的第三个节点，返回那个节点

既然有要查找从头开始的，那倒数的节点怎么去找呢（当然指的是单向链表啦）

这不简单嘛，直接根据链表的长度来减去倒数第k个节点的k就回到上面的步骤来了嘛，但是要知道链表的长度就得遍历一遍链表，之后还要遍历一遍链表才能找到那个节点，这不就显得有点麻烦嘛🤪

这里可以借助双指针就能解决这一问题：

• 定义两个指针pre、last指向链表的头节点，然后让last先走k下

• 之后再让pre和last一起走，当last走到链表尾部的时候，pre所指向的也即是要找的节点

用代码表示出来大概是这样：

// 返回倒数第k个节点public ListNode getKthFromEnd(ListNode head, int k) {    ListNode last = head, pre = head;    // 先让last走k下    while (k-- > 0) {        last = last.next;    }
    while (last != null) {        last = last.next;        pre = pre.next;    }    return pre;}

由于链表中的数据只能是按照next依次往后查找，所以时间复杂度是O(n)

向链表中插入节点

向链表中某一位置插入节点只需 改变上一位置的next指向要插入的节点，以及将 要插入节点的next指向下一位置的节点即可

如果要插入的位置在链表头部或者是链表尾部呢🧐

其实都差不多，只是要注意头部插入时要将插入节点变为头部节点，尾部插入时插入节点要指向null

不同于数组插入元素时要考虑扩容的问题，链表在内存空间允许的情况下是可以插入很多很多的节点的

删除链表中节点

与插入节点类似，可以分为头部删除、中间删除以及尾部删除

这里朋友们应该都能想到是什么样子的，我就稍稍偷偷懒吧🤥

这里还想再多提一句，被删除的节点哪去了呢？许多高级语言，比如Java都有垃圾回收机制，所以不用那么在意它们，只要没有外部引用去指向它们，被删除的节点就会被自动回收

另外如果不考虑查找节点的过程，只是插入或者删除节点操作，时间复杂度都为O(1)

都看到这了，不如来一些经典的链表题目再熟悉下吧

链表经典题目

206. 反转链表

题目大致就是反转一个单链表，也就是说原来的链表头节点变为尾部节点，并且指向null

因为是要反转，可以把这些节点都放在一个容器中，例如ArrayList，然后通过工具类的自带方法Collections.reverse()将其反转，再在内部将这些节点用next关联起来形成一个新链表，最后尾节点指向null

这方法很简单，不过如果要求不用外部空间，那又怎么搞呢🙁

这时可以用双指针迭代来解决：

• 定义一个指针pre指向null，一个指针cur指向链表头节点

• 每次迭代时cur.next = pre，之后cur和pre都向前走一步，不过这里还需要一个指针tmp指向cur下一步的位置，那么pre下一步的位置也就是cur的位置

可以发现，最后pre指向的是反转后的链表头节点，cur指向的是null，所以循环条件也能得出来，用代码表示出来大概是这样：

public ListNode reverseList(ListNode head) {    if (head == null || head.next == null) {        return head;    }
    ListNode pre = null, cur = head;    while (cur != null) {        ListNode tmp = cur.next; // 记录cur下一步的位置        cur.next = pre;        // pre和cur都前进一步        pre = cur;        cur = tmp;    }    return pre;}

这道题还可以用递归来解，不妨来看看链表用递归大概是什么样子的

先说说递归，我们知道，计算机在执行递归程序时，会专门分配一块内存，用来存储 “方法调用栈”：

• “方法调用栈” 包括进栈和出栈两个行为

• 当进入一个新方法时，执行入栈操作，把调用的方法和参数压入栈中

• 当遇到终止条件方法返回时，执行出栈操作，把调用的方法和参数都从栈中弹出

在这里，很显然终止条件是当前节点或者下一节点为null时返回；那方法内部执行的操作又是什么呢？因为是要反转链表，也就是说当前节点的下一节点的next要指向当前节点上（有点绕，不妨结合代码和图看看）

public ListNode reverseList(ListNode head) {    // 终止条件    if (head == null || head.next == null) {        return head;    }        // 这里递归遇到终止条件时cur指向链表尾节点，同时也是反转后的链表头节点    ListNode cur = reverseList(head.next);    head.next.next = head; // 完成反转操作    head.next = null; // 这里head变成了尾节点，尾节点指向null    return cur;}

其实这里还可以利用栈先进后出的特性，将所有节点先入栈，当全部入栈后再一个一个出栈串起来，形成一个新的链表

不过这里不详细展开了，要讲清楚的话就得把栈说清楚，所以想放到后面文章来讲，有兴趣的朋友可以自己实现一下，还可以参考这道题445. 两数相加 II

141. 环形链表

题目大致意思是给定一个链表，判断这个链表是否有环（也就是说链表尾节点next指向另一节点上），如果存在环，则返回true，否则，返回false

因为是会遇到重复元素，自己最开始想到的是利用Set存储的是不重复的元素集合 来实现，这种方法也是容易想到且容易理解的，不过还是可以优化的

举个例子，学生时代总是跑过环形跑道的吧，如果两个人的速度不同，无论两个人的起点在哪，那么总能在跑道的某一处相遇（其实相当于一个追及问题）

那么类比过来，两个人换成双指针，速度不同（也就相当于指针每次往后走的步数不同）如果链表有环，那么一定是可以相遇的，比如快指针每次走两步，慢指针每次走一步

这里如果不存在环的话，快指针走到链表尾时，慢指针指向的是链表中间节点的位置哦（当然有奇数个节点与偶数个节点的区分）

那么用代码表示出来大概是这样子的：

public boolean hasCycle(ListNode head) {    if (head == null || head.next == null) {        return false;    }    // 快慢两个指针    ListNode fast = head, slow = head;    while (fast != null && fast.next != null) {        fast = fast.next.next;        slow = slow.next;        // 如果相遇，则说明有环，直接返回true，否则不存在环，跳出循环返回false        if (fast == slow) {            return true;        }    }    return false;}

这里规定的快指针走两步，慢指针走一步，但只需要快慢指针速度不同即可相遇，那么快指针走三步，慢指针走一步抑或是快指针走四步，慢指针走两步都是可以的（不过要注意循环条件也得跟着变）

这里只是简单的返回true或者false，如果是要返回链表开始入环时的第一个节点呢🙁

因为fast和slow指针相遇时可能不在入环时的第一个节点，所以就可以借助相遇时走过的距离加上数学分析来搞定（这里为了方便假定fast每次走两步，slow每次走一步）：

• 假设链表共有a+b个节点（其中链表头节点到链表环入口有a个节点，链表环有b 个节点）

• 假设fast和slow指针相遇时分别走了f步和s步，所以就有：

• fast走的步数是slow的两倍：f = 2s
  

• fast必须比slow多走了n个环才能相遇：f = s + nb（简单来说当两人在跑一千米相遇时，你跑得慢，那别人就已经超你一圈了）这里是有前面的a个节点，所以可能会多走n个环

• 由此得s = nb，接下来只要再找出a为多少就可以找到链表入环时的第一个节点：

• 现在slow已经走了n个环，那么再有一指针cur从链表头开始走，随slow一起走了a步时两指针又会相遇，此时相遇的节点就为要找的节点

剑指 Offer 52. 两个链表的第一个公共节点

如果说上面的环形链表是找一个链表中相同的节点，那么这里就是找两个链表中相同的节点

同样的，可以利用集合set来解决，也就是将一个链表的节点全部存放到set中，然后遍历另一个链表中的节点，判断这个节点在set中是否存在

还有一种方法就是利用两个链表的长度来解决，如果知道了两个链表的长度的话，先将长的链表往后移，当然是边走边比较啦，直到两个链表的长度相同时，两链表再一起边走边比较。不过在前面有说道要知道一链表的长度就要先遍历一遍链表，所以这里相当于要遍历两遍链表，不妥

上面两种方法简单带过了，其实主要是想讲下面的方法，只需要遍历一遍，而且很快就讲完了哦

因为不知道两链表的长度是不是一样的，所以才会先遍历一遍找出一个链表的长度来，那如果两链表走的距离都是两链表的长度加起来的话，不就一样了嘛：

• 指针curA从链表A头节点走到尾，再从链表B头节点走到尾

• 指针curB从链表B头节点走到尾，再从链表A头节点走到尾

咋一看这好像死循环了呀，其实链表尾节点是要指向null的，所以如果没有相同节点的话两指针就会指向null

用代码表示出来大概是这样：

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {    if (headA == null || headB == null) {        return null;    }            ListNode curA = headA, curB = headB;    while (curA != curB) {        curA = curA == null ? headB : curA.next;        curB = curB == null ? headA : curB.next;    }    return curA;}

86. 分隔链表

提出这道题主要是想讲一下怎么用前面提到过的哑节点

题目大致是将一个链表进行分隔，所有小于x的节点排在大于或等于x的节点之前，且初始相对位置不变，比如这样：

前面说到，哑节点就是一个虚拟节点作为头节点，链表第一个元素其实是第二个节点，那么这里可以

• 定义两个哑节点，一个哑节点指向的链表放小于x的，另一个放大于或等于x的

• 遍历完最开始的链表后，将小于x的链表拼在另一个前就成了新的链表

用代码表示出来大概是这样：

public ListNode partition(ListNode head, int x) {    ListNode smallHead = new ListNode(0); // 放小于 x 的节点    ListNode smallTail = smallHead;       // 指向 smallHead 的尾节点    ListNode bigHead = new ListNode(0);   // 放大于或等于 x 的节点    ListNode bigTail = bigHead;           // 指向 bigHead 的尾节点            while (head != null) {        if (head.val < x) {            smallTail.next = head;            smallTail = smallTail.next;        } else {            bigTail.next = head;            bigTail = bigTail.next;        }        head = head.next;    }    smallTail.next = bigHead.next;       // 将两链表串起来    bigTail.next = null;     return smallHead.next;}

朋友们如果觉得这篇文章有帮助的话，不如点个赞再走吧😃