动画 | 什么是链表？

如果说数据结构是算法的基础，那么数组和链表就是数据结构的基础。因为像堆，栈，树，图等比较复杂的数组结基本上都可以由数组和链表来表示，所以掌握数组和链表的基本操作十分重要。

今天就来看看 链表的基本操作及其在面试中的常见解题思路， 本文将从以下几个点来讲解链表的核心知识

1. 什么是链表，链表的优缺点
2. 链表的表示及基本操作
3. 面试中链表的常见解题思路---翻转

什么是链表

相信大家已经开始迫不及待地想用链表解题了，不过在开始之前我们还是要先来温习下链表的定义，以及它的优势与劣势，磨刀不误砍柴功！

链表的定义

链表是物理存储单元上 非连续 的、 非顺序 的存储结构，它是由一个个结点，通过指针来联系起来的，其中每个结点包括数据和指针。

链表的 非连续 ， 非顺序 ，对应数组的 连续 ， 顺序 ，我们来看看整型数组 1，2，3，4 在内存中是如何表示的

可以看到数组的每个元素都是连续紧邻分配的，这叫连续性，同时由于数组的元素占用的大小是一样的，在 Java 中 int 型大小固定为 4 个字节,所以如果数组的起始地址是 100， 由于这些元素在内存中都是连续紧邻分配的，大小也一样，可以很容易地找出数组中任意一个元素的位置，比如数组中的第三个元素起始地址为 100 + 2 * 4 = 108,这就叫顺序性。查找的时间复杂度是O(1),效率很高！

那链表在内存中是怎么表示的呢

可以看到每个结点都分配在 非连续 的位置，结点与结点之间通过指针连在了一起，所以如果我们要找比如值为 3  的结点时，只能通过结点 1 从头到尾遍历寻找，如果元素少还好，如果元素太多（比如超过一万个），每个元素的查找都要从头开始查找，时间复杂度是O(n)，比起数组的 O(1)，差距不小。

除了查找性能链表不如数组外，还有一个优势让数组的性能高于链表,这里引入 程序局部性原理 ，啥叫程序局部性原理。

我们知道 CPU 运行速度是非常快的，如果 CPU 每次运算都要到内存里去取数据无疑是很耗时的，所以在 CPU 与内存之间往往集成了挺多层级的缓存，这些缓存越接近CPU，速度越快，所以如果能提前把内存中的数据加载到如下图中的 L1, L2, L3 缓存中，那么下一次 CPU 取数的话直接从这些缓存里取即可，能让CPU执行速度加快，那什么情况下内存中的数据会被提前加载到 L1,L2,L3 缓存中呢，答案是当某个元素被用到的时候，那么这个元素地址附近的的元素会被提前加载到缓存中

以上文整型数组 1，2，3，4为例，当程序用到了数组中的第一个元素（即 1）时，由于 CPU 认为既然 1 被用到了，那么紧邻它的元素 2，3，4 被用到的概率会很大，所以会提前把 2，3，4 加到 L1,L2,L3 缓存中去，这样 CPU 再次执行的时候如果用到 2，3，4，直接从 L1,L2,L3 缓存里取就行了，能提升不少性能

画外音： 如果把 CPU 的一个时种看成一秒，则从 L1 读取数据需要 3 秒，从 L2 读取需要 11 秒，L3读取需要 25秒，而从内存读取呢，需要 1 分 40 秒，所以程序局部性原理能对 CPU 执行性能有很大的提升

而链表呢，由于链表的每个结点在内存里都是随机分布的，只是通过指针联系在一起，所以这些结点的地址并不相邻，自然无法利用 程序局部性原理 来提前加载到 L1,L2,L3 缓存中来提升程序性能。

画外音： 程序局部性原理是计算机中非常重要的原理，这里不做展开，建议大家查阅相关资料详细了解一下

如上所述，相比数组，链表的 非连续 ， 非顺序 确实让它在性能上处于劣势，那什么情况下该使用链表呢？考虑以下情况

• 大内存空间分配

由于数组空间的 连续性 ，如果要为数组分配 500M 的空间，这 500M 的空间必须是 连续的 ，未使用的，所以在内存空间的分配上数组的要求会比较严格，如果内存碎片太多，分配连续的大空间很可能导致失败。而链表由于是非连续的，所以这种情况下选择链表更合适。

• 元素频繁删除和插入

如果涉及到元素的频繁删除和插入，用链表就会高效很多，对于数组来说，如果要在元素间插入一个元素，需要把其余元素一个个往后移（如图示），以为新元素腾空间（同理，如果是删除则需要把被删除元素之后的元素一个个往前移），效率上无疑是比较低的。

(在 1，2 间插入 5，需要把2，3，4 同时往后移一位)

而链表的插入删除相对来说就比较简单了，修改指针位置即可，其他元素无需做任何移动操作（如图示：以插入为例）

综上所述：如果数据以查为主，很少涉及到增和删，选择数组，如果数据涉及到频繁的插入和删除，或元素所需分配空间过大，倾向于选择链表。

说了这么多理论，相信读者对数组和链表的区别应该有了更深刻地认识了，尤其是 程序局部性原理 ，是不是开了不少眼界^_^

如果面试中问到数组和链表的区别能回答到程序局部性原理，会是一个 非常大的亮点 ！

接下来我们来看看链表的表现形式和解题技巧。

链表的表示

由于链表的特点（查询或删除元素都要从头结点开始）,所以我们只要在链表中定义头结点即可,另外如果要频繁用到链表的长度，还可以额外定义一个变量来表示。

需要注意的是这个头结点的定义是有讲究的，一般来说头结点有两种定义形式，一种是直接以某个元素结点为头结点,如下

一种是以一个虚拟的节点作为头结点，即我们常说的 哨兵 ，如下

定义这个哨兵有啥好处呢，假设我们不定义这个哨兵，来看看链表及添加元素的基本操作怎么定义的

/**
* 链表中的结点，data代表节点的值，next是指向下一个节点的引用
 */
class Node {
    int data;// 结点的数组域，值
    Node next = null;// 节点的引用，指向下一个节点
    public Node(int data) {
        this.data = data;
    }
}

/**
* 链表
 */
public class LinkedList {
    int length = 0; // 链表长度，非必须，可不加
    Node head = null; // 头结点

    public void addNode(int val) {
        if (head == null) {
            head = new Node(val);
        } else {
            Node tmp = head;
            while (tmp.next != null) {
                tmp.next = tmp;
            }
            tmp.next = new Node(val);
        }
    }
}

发现问题了吗，注意看下面代码

有两个问题：

1. 每插入一个元素都要对头结点进行判空比较，如果一个链表有很多元素需要插入，就需要进行很多次的判空处理，不是那么高效
2. 头结点与其他结点插入逻辑不统一（一个需要判空后再插入，一个不需要判空直接插入）,从程序逻辑性来说不是那么合理（因为结点与结点是平级，添加逻辑理应相同）

如果定义了哨兵结点，以上两个问题都可解决，来看下使用哨兵结点的链表定义

public class LinkedList {
    int length = 0; // 链表长度，非必须，可不加
    Node head = new Node(0); // 哨兵结点
    public void addNode(int val) {
        Node tmp = head;
        while (tmp.next != null) {
            tmp.next = tmp;
        }
        tmp.next = new Node(val);
    }
}

可以看到，定义了哨兵结点的链表逻辑上清楚了很多,不用每次插入元素都对头结点进行判空，也统一了每一个结点的添加逻辑。

所以之后的习题讲解中我们使用的链表都是使用定义了哨兵结点的形式。

做了这么多前期的准备工作，终于要开始我们的正餐了：链表解题常用套路--翻转！

链表常见解题套路

热身赛

既然我们要用链表解题，那我们首先就构造一个链表吧

题目：给定数组 1，2，3，4 构造如下链表 head-->4---->3---->2---->1

看清楚了，是逆序构造链表！顺序构造我们都知道怎么构造，对每个元素持续调用上文代码定义的 addNode 方法即可（即尾插法），与尾插法对应的，是 头插法 ，即把每一个元素插到头节点后面即可，这样就能做到逆序构造链表，如图示（以插入1，2 为例）

头插法比较简单，直接上代码,直接按以上动图的步骤来完成逻辑，如下

public class LinkedList {
    int length = 0; // 链表长度，非必须，可不加
    Node head = new Node(0); // 哨兵节点
    
     // 头插法
    public void headInsert(int val) {
        // 1.构造新结点
        Node newNode = new Node(val);
        // 2.新结点指向头结点之后的结点
        newNode.next = head.next;
        // 3.头结点指向新结点
        head.next = newNode;
    }

    public static void main(String[] args) {
        LinkedList linkedList = new LinkedList();
        int[] arr = {1,2,3,4};
        // 头插法构造链表
        for (int i = 0; i < arr.length; i++) {
            linkedList.headInsert(arr[i]);
        }
        // 打印链表,将打印 4-->3-->2-->1
        linkedList.printList();
    }
}

小试牛刀

现在我们加大一下难度，来看下曾经的 Google 面试题：给定单向链表的头指针和一个节点指针，定义一个函数在 O(1) 内删除这个节点。

如图示：给定值为 2 的结点，如何把这个结点给删了。

我们知道，如果给定一个结点要删除它的后继结点是很简单的，只要把这个结点的指针指向后继结点的后继结点即可

如图示：给定结点 2，删除它的后继结点 3， 把结点 2 的 next 指针指向 3 的后继结点 4 即可。

但给定结点 2，该怎么删除结点 2 本身呢，注意题目没有规定说不能改变结点中的值，所以有一种很巧妙的方法，狸猫换太子！我们先通过结点 2 找到结点 3，再把节点 3 的值赋给结点 2，此时结点 2 的值变成了 3，这时候问题就转化成了上图这种比较简单的需求，即根据结点 2 把结点 3 移除即可，看图

不过需要注意的是这种解题技巧只适用于被删除的指定结点是中间结点的情况，如果指定结点是尾结点，还是要老老实实地找到尾结点的前继结点，再把尾结点删除，代码如下

/**
 * 删除指定的结点
 * @param deletedNode
 */
public void removeSelectedNode(Node deletedNode) {
    // 如果此结点是尾结点我们还是要从头遍历到尾结点的前继结点，再将尾结点删除
    if (deletedNode.next == null) {
        Node tmp = head;
        while (tmp.next != deletedNode) {
            tmp = tmp.next;
        }
        // 找到尾结点的前继结点，把尾结点删除
        tmp.next = null;
    } else {
        Node nextNode = deletedNode.next;
        // 将删除结点的后继结点的值赋给被删除结点
        deletedNode.data = nextNode.data;
        // 将 nextNode 结点删除
        deletedNode.next = nextNode.next;
        nextNode.next = null;
    }
}

入门到进阶:链表翻转

接下来我们会重点看一下链表的翻转，链表的翻转可以衍生出很多的变形，是面试中非常热门的考点，基本上考链表必考翻转！所以掌握链表的翻转是必修课！

什么是链表的翻转:给定链表 head-->4--->3-->2-->1 ，将其翻转成 head-->1-->2-->3-->4 ，由于翻转链表是如此常见，如此重要，所以我们分别详细讲解下如何用递归和非递归这两种方式来解题

• 递归翻转

关于递归的文章之前写了三篇，如果之前没读过的，强烈建议点击 这里 查看，总结了递归的常见解题套路,给出了递归解题的常见四步曲，如果看完对以下递归的解题套路会更加深刻，这里不做赘述了，我们直接套递归的解题思路：

首先我们要查看翻转链表是否符合递归规律：问题可以分解成 具有相同解决思路 的子问题，子子问题...，直到最终的子问题再也无法分解。

要翻转 head--->4--->3-->2-->1 链表，不考虑 head 结点，分析 4--->3-->2-->1，仔细观察我们发现只要先把 3-->2-->1 翻转成 3

图：翻转链表主要三步骤

只要按以上步骤定义好这个翻转函数的功能即可， 这样由于子问题与最初的问题具有 相同的解决思路 ，拆分后的子问题持续调用这个翻转函数即可达到目的。

注意看上面的步骤1，问题的规模是不是缩小了（如下图），从翻转整个链表变成了只翻转部分链表！问题与子问题都是从某个结点开始翻转，具有 相同的解决思路 ，另外当缩小到只翻转一个结点时，显然是终止条件，符合递归的条件！之后的翻转 3-->2-->1, 2-->1 持续调用这个定义好的递归函数即可！

既然符合递归的条件，那我们就可以套用 递归四步曲 来解题了（注意翻转之后 head 的后继节点变了，需要重新设置！别忘了这一步）

1、定义递归函数,明确函数的功能 根据以上分析，这个递归函数的功能显然是翻转某个节点开始的链表，然后返回新的头结点

/**
 * 翻转结点 node 开始的链表
 */
public Node invertLinkedList(Node node) {
}

2、寻找递推公式 上文中已经详细画出了翻转链表的步骤，简单总结一下递推步骤如下

• 针对结点 node (值为 4), 先翻转 node 之后的结点   invert(node->next) ,翻转之后 4---> 3--->2--->1 变成了 4---> 3
• 再把 node 节点的下个节点（3）指向 node，node 的后继节点设置为空（避免形成环），此时变成了 4
• 返回新的头结点，因为此时新的头节点从原来的 4 变成了 1，需要重新设置一下 head

3、将递推公式代入第一步定义好的函数中，如下 (invertLinkedList)

/**
 * 递归翻转结点 node 开始的链表
 */
public Node invertLinkedList(Node node) {
    if (node.next == null) {
        return node;
    }

    // 步骤 1: 先翻转 node 之后的链表
    Node newHead = invertLinkedList(node.next);

    // 步骤 2: 再把原 node 节点后继结点的后继结点指向 node，node 的后继节点设置为空(防止形成环)
    node.next.next = node;
    node.next = null;

    // 步骤 3: 返回翻转后的头结点
    return newHead;
}

public static void main(String[] args) {
    LinkedList linkedList = new LinkedList();
    int[] arr = {4,3,2,1};
    for (int i = 0; i < arr.length; i++) {
        linkedList.addNode(arr[i]);
    }
    Node newHead = linkedList.invertLinkedList(linkedList.head.next);
    // 翻转后别忘了设置头结点的后继结点！
    linkedList.head.next = newHead;
    linkedList.printList();      // 打印 1，2，3，4
}

画外音： 翻转后由于 head 的后继结点变了，别忘了重新设置哦！

4、计算时间/空间复杂度 由于递归调用了 n 次 invertLinkedList 函数，所以时间复杂度显然是 O(n), 空间复杂度呢，没有用到额外的空间，但是由于递归调用了  n 次 invertLinkedList 函数，压了 n 次栈，所以空间复杂度也是 O(n)。

递归一定要从 函数的功能 去理解，从函数的功能看，定义的递归函数清晰易懂，定义好了之后，由于问题与被拆分的子问题具有相同的解决思路，所以子问题只要持续调用定义好的功能函数即可，切勿层层展开子问题，此乃递归常见的陷阱！仔细看函数的功能，其实就是按照下图实现的。(对照着代码看，是不是清晰易懂^_^)

• 非递归翻转链表（迭代解法）

我们知道递归比较容易造成栈溢出，所以如果有其他时间/空间复杂度相近或更好的算法，应该优先选择非递归的解法,那我们看看如何用迭代来翻转链表，主要思路如下

步骤 1：定义两个节点：pre, cur ，其中 cur 是 pre 的后继结点，如果是首次定义， 需要把 pre 指向 cur 的指针去掉，否则由于之后链表翻转，cur 会指向 pre， 就进行了一个环(如下)，这一点需要注意

步骤2：知道了 cur 和 pre,翻转就容易了，把 cur 指向 pre 即可，之后把 cur 设置为 pre ，cur 的后继结点设置为 cur 一直往前重复此步骤即可,完整动图如下

注意：同递归翻转一样，迭代翻转完了之后 head 的后继结点从 4 变成了 1，记得重新设置一下。

知道了解题思路，实现代码就容易多了，直接上代码

/**
 * 迭代翻转
 */
public void iterationInvertLinkedList() {
    // 步骤 1
    Node pre = head;
    Node cur = pre.getNext();
    pre.setNext(null);   // pre 是头结点，避免翻转链表后形成环

    // 步骤 2
    while (cur != null) {
        /**
         * 务必注意!!!：在 cur 指向 pre 之前一定要先保留 cur 的后继结点，不然如果 cur 先指向 pre，之后就再也找不到后继结点了
         */
        Node next = cur.getNext();
        cur.setNext(pre);
        pre = cur;
        cur = next;
    }
    // 此时 pre 指向的是原链表的尾结点，翻转后即为链表 head 的后继结点
    head.next = pre;
}

用迭代的思路来做由于循环了 n 次，显然时间复杂度为 O(n),另外由于没有额外的空间使用，也未像递归那样调用递归函数不断压栈，所以空间复杂度是 O(1),对比递归，显然应该使用迭代的方式来处理！

花了这么大的精力我们总算把翻转链表给搞懂了，如果大家看了之后几道翻转链表的变形，会发现我们花了这么大篇幅讲解翻转链表是值得的。

接下来我们来看看链表翻转的变形

变形题 1 ：给定一个链表的头结点 head,以及两个整数 from 和 to ,在链表上把第 from 个节点和第 to 个节点这一部分进行翻转。例如：给定如下链表，from = 2, to = 4 head-->5--> 4-->3-->2 -->1 将其翻转后，链表变成 head-->5---> 2-->3-->4 -->1

有了之前翻转整个链表的解题思路，现在要翻转部分链表就相对简单多了,主要步骤如下:

1. 根据 from 和 to 找到 from-1, from, to,  to+1 四个结点(注意 临界条件 ，如果 from 从头结点开始，则 from-1 结点为空, 翻转后需要把 to 设置为头结点的后继结点， from 和 to 结点也可能超过尾结点,这两种情况不符合条件不翻转)。
2. 对 from 到 to 的结点进行翻转
3. 将 from-1 节点指向 to 结点，将 from 结点指向 to + 1 结点

知道了以上的思路，代码就简单了,按上面的步骤1，2，3 实现，注释也写得很详细，看以下代码（对 from 到 to 结点的翻转我们使用迭代翻转，当然使用递归也是可以的，限于篇幅关系不展开，大家可以尝试一下）。

/**
 * 迭代翻转 from 到 to 的结点
 */
public void iterationInvertLinkedList(int fromIndex, int toIndex) throws Exception {

    Node fromPre = null;            // from-1结点
    Node from = null;               // from 结点
    Node to = null;                 // to 结点
    Node toNext = null;             // to+1 结点

    // 步骤 1：找到  from-1, from, to,  to+1 这四个结点
    Node tmp = head.next;
    int curIndex = 1;      // 头结点的index为1
    while (tmp != null) {
        if (curIndex == fromIndex-1) {
            fromPre = tmp;
        } else if (curIndex == fromIndex) {
            from = tmp;
        } else if (curIndex == toIndex) {
            to = tmp;
        } else if (curIndex == toIndex+1) {
            toNext = tmp;
        }
        tmp = tmp.next;
        curIndex++;
    }

    if (from == null || to == null) {
        // from 或 to 都超过尾结点不翻转
        throw new Exception("不符合条件"