大家都知道程咬金的“三板斧”这个绝技，那今天我也给你介绍解决链表问题的“三板斧”：假头、新链表、双指针。由于内容比较多，所以这里拆分了上、下两篇来讲解，通过这一讲的学习，你可以深入理解带假头链表的 6 种最基本的操作。

链表作为一种重要的数据结构，无论是在工作中，还是在面试中都经常出现。这种数据结构可以用在很多地方，比如内核的消息队列、缓存管理、跳表，B+ 树等。

有的面试官非常喜欢考察面试者的链表知识，主要有以下 3 个原因：

操作链表需要非常小心，考虑各种边界情况；

链表结构简单，但是查找、交换、翻转都非常容易出错；

解决链表问题，需要有一定的算法思想，但是又并不太难。在面试过程中，需要你想到解题方法并实现出来，更加考察应试者的工程能力。

注：由于链表题的求解重点不在思路，所以这里，我们不再采用“四步分析法”找规律来讲解链表。

在本讲我会介绍一些解决链表的新方法与新思路，带你踏上“链表的奇幻之旅”。

三板斧中的第一斧：假头

假头通常也叫作 Dummy Head 或者“哑头”。实际上，就是在链表前面，加上一个额外的结点。此时，存放了 N 个数据的带假头的链表，算上假头一共有 N+1 个结点。

额外的结点不会存放有意义的数据。那么它的作用是什么呢？

你可以这样理解，添加假头后，可以省略掉很多空指针的判断，链表的各种操作会变得更加简洁。接下来，我们看一下关于链表的各种操作，今天主要介绍 6 种最基本的操作：

初始化

追加结点

头部插入结点

查找结点

插入指定位置之前

删除结点

为了将这 6 种基本的操作串起来，我想到了一道考察设计链表的面试题，题目要求应试者将这 6 种基本的操作加以实现：注释中的 /code here/ 部分是填写相应的 6 种功能代码。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

// 实现单链表
class MyLinkedList {
  // 链表结点的定义
  class ListNode {
    // val用来存放链表中的数据
    public int val = 0;
    // next指向下一个结点
    public ListNode next = null;
    public ListNode() {}
    public ListNode(int x) {
      val = x;
    }
  }
  /** code here: 初始化链表*/
  public MyLinkedList() {
  }
  public void addAtTail(int val) {
    /* code here: 将值为 val 的结点追加到链表尾部*/
  }
  public void addAtHead(int val) {
    /* code here: 插入值val的新结点，使它成为链表的第一个结点*/
  }
  public int get(int index) {
    /* code here: 获取链表中第index个结点的值。如果索引无效，则返回-1。*/
    // index从0开始。
  }
  public void addAtIndex(int index, int val) {
    // code here:
    // 在链表中的第 index 个结点之前添加值为 val  的结点。
    // 1. 如果 index 等于链表的长度，则该结点将附加到链表的末尾。
    // 2. 如果 index 大于链表长度，则不会插入结点。
    // 3. 如果index小于0，则在头
  }
  public void deleteAtIndex(int index) {
    /* code here: 如果索引index有效，则删除链表中的第index个结点。*/
  }
}

初始化

初始化假头链表，首先，我们需要 new 出一个链表结点，并且让链表的 dummy 和 tail 指针都指向它，代码如下（解析在注释里）：

1
2
3
4
5
6
7

  /** code here: 初始化链表*/
  // 初始化dummy
  private ListNode dummy = new ListNode();
  // 初始化链表tail指针
  private ListNode tail = dummy;
  // 初始化链表的长度，此时为0
  private int length = 0;

代码：Java/C++/Python

初始化完成后，链表已经有了一个结点，但是此时，整个链表中还没有任何数据。因此，在后文中，我们说一个空链表的时候，就是指已经初始化好的带假头链表。

相信你已经学会了这几行代码的精髓，下面我要考考你了。

小测验：一个带假头的链表初始化的时候，哪个指针是空的？

A. dummy 指针

B. tail 指针

C. dummy 和 tail 指针

D. dummy.next 指针

正确答案 D

dummy.next 指针。因为带假头的链表初始化以后，dummy 和 tail 都是指向了 new 出来的结点，但是这个时候，还没有任何其他结点进来，所以 dummy.next 为空。

虽然 dummy 和 tail 初始化完成之后，都指向同一个结点。但是这两者还有一个有趣的特点，叫“动静结合”。

静：dummy 指针初始化好以后，永远都是静止的，再也不会动了。

动：tail 指针在链表发生变动的时候，就需要移动调整。

接下来，我们再来看看追加结点。

追加结点

尾部添加新结点操作只有两步，代码如下（解析在注释里）：

1
2
3
4
5
6
7
8
9

  public void addAtTail(int val) {
    /* code here: 将值为 val 的结点追加到链表尾部*/
    // 尾部添加一个新结点
    tail.next = new ListNode(val);
    // 移动tail指针
    tail = tail.next;
    // 链表长度+1
    length++;
  }

代码：Java/C++/Python

这段代码的执行过程如下图所示：

小测验：这里 tail 指针需要判断是否为空吗？

A. 需要

B. 不需要

正确答案 B

带假头的链表初始化之后，可以保证 tail 指针永远非空，因此，也就可以直接去修改 tail.next 指针，省略掉了关于 tail 指针是否为空的判断。比如，空链表追加新结点时执行过程如下动图所示：

头部插入结点

需要插入的新结点为 p，插入之后，新结点 p 会成为第一个有意义的数据结点。通过以下 3 步可以完成头部插入：

新结点 p.next 指向 dummy.next；

dummy.next 指向 p；

如果原来的 tail 指向 dummy，那么将 tail 指向 p。

对应的代码如下（解析在注释里）：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

  public void addAtHead(int val) {
    /* code here: 插入值val的新结点，使它成为链表的第一个结点*/
     // 生成一个结点，存放的值为val
    ListNode p = new ListNode(val);
    // 将p.next指向第一个结点
    p.next = dummy.next;
    // dummy.next指向新结点，使之变成第一个结点
    dummy.next = p;
    // 注意动静结合原则，添加结点时，注意修改tail指针。
    if (tail == dummy) {
      tail = p;
    }
    length++;
  }

代码：Java/C++/Python

代码执行流程如下动图所示：

这段代码有趣的地方在于，当链表为空的时候，它依然是可以工作的。因为虽然链表是空的，但是由于有 dummy 结点的存在，代码并不会遇到空指针，此时工作流程如下：

下面请你通过小测验自我检验。

小测验：在插入结点的时候，哪一步最容易遗忘？

A. new 一个假头

B. new 一个新结点

C. 修改 next 指针

D. 修改 tail 指针

正确答案 D

如果链表添加了结点，或者删除了结点，一定要记得修改 tail 指针。如果忘了修改，那么就不能正确地获取链表的尾指针，从而错误地访问链表中的数据。这一点非常重要，无数人在这个坑上翻过车。

查找结点

在查找索引值为 index（假设 index 从 0 开始）的结点时，你需要注意，大多数情况下，返回指定结点前面的一个结点 prev 更加有用。

好处有以下两个方面：

通过 prev.next 就可以访问到你想要找到的结点，如果没有找到，那么 prev.next 为 null；

通过 prev 可以方便完成后续操作，比如在 target 前面 insert 一个新结点，或者将 target 结点从链表中移出去。

因此，如果要实现 get 函数，我们应该先实现一个 getPrevNode 函数。具体的操作如下（解析在注释里）：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

private ListNode getPrevNode(int index) {
  /*返回index结点的前驱结点，如果index不存在，那么返回dummy*/
  // 初始化front与back，分别一前一后
  ListNode front = dummy.next;
  ListNode back = dummy;
  // 在查找的时候，front与back总是一起走
  for (int i = 0; i < index && front != null; i++) {
    back = front;
    front = front.next;
  }
  // 把back做为prev并且返回
  return back;
}

代码：Java/C++/Python

程序的执行过程如下：

有了假头的帮助，这段查找代码就非常健壮了，可以处理以下 2 种情况：

如果 target 在链表中不存在，此时 prev 返回链表的最后一个结点；

如果为空链表（空链表指只有一个假头的链表），此时 prev 指向 dummy。也就是说，返回的 prev 指针总是有效的。

借助 getPrevNode 函数，我们就可以写出 get 函数了，代码如下（解析在注释里）：

1
2
3
4
5
6
7
8
9

public int get(int index) {
  // 获取链表中第 index 个结点的值。如果索引无效，则返回-1。
  // index从0开始
  if (index < 0 || index >= length) {
    return -1;
  }
  // 因为getPrevNode总是返回有效的结点，所以可以直接取值。
  return getPrevNode(index).next.val;
}

代码：Java/C++/Python

插入指定位置之前

插入指定位置的前面，有 4 个需求。

如果 index 大于链表长度，则不会插入结点。

如果 index 等于链表的长度，则该结点将附加到链表的末尾。

如果 index 小于 0，则在头部插入结点。

否则在指定位置前面插入结点。

其中，Case 1~3 较容易处理。可以直接写。重点在于 Case 4。现在你已经有了 getPrevNode() 函数，就可以比较容易地写出 Case 4 的代码，思路如下：

使用 getPrevNode() 函数拿到 index 之前的结点 pre；

在 pre 的后面添加一个新结点。

以下是具体的 Case 1~4 的操作过程，具体的代码如下（解析在注释里）：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

public void addAtIndex(int index, int val) {
  if (index > length) {
    // Case 1.如果 index 大于链表长度，则不会插入结点。
    return;
  } else if (index == length) {
    // Case 2.如果 index 等于链表的长度，则该结点将附加到链表的末尾。
    addAtTail(val);
  } else if (index <= 0) {
    // Case 3. 如果index小于0，则在头部插入结点。
    addAtHead(val);
  } else {
    // Case 4.
    // 得到index之前的结点pre
    ListNode pre = getPrevNode(index);
    // 在pre的后面添加新结点
    ListNode p = new ListNode(val);
    p.next = pre.next;
    pre.next = p;
    // 注意修改长度
    length++;
  }
}

代码：Java/C++/Python

注意： 这里有一个新手很容易犯错的地方，我单独给你提取出来：

1
2

    p.next = pre.next;
    pre.next = p;

你一定要记住，这两行代码的顺序打死也不能换。一旦交换，链表的操作就会出现错误，再也不能正常工作了。此时出错的情况就会变成下图这样：

删除结点

删除结点操作是给定要删除的下标 index（下标从 0 开始），删除的情况分 2 种：

如果 index 无效，那么什么也不做；

如果 index 有效，那么将这个结点删除。

上面这 2 种情况中，Case 1 比较容易处理，相对要麻烦一些的是 Case 2。要删除 index 结点，最好是能找到它前面的结点。有了前面的结点，再删除后面的结点就容易多了。不过我们已经有了 getPrevNode 函数，所以操作起来还是很简单的。

以下是具体的操作过程（解析在注释里）：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

// 如果索引 index 有效，则删除链表中的第 index 个节点。
public void deleteAtIndex(int index) {
  // Case 1. 如果index无效，那么什么也不做。
  if (index < 0 || index >= length) {
    return;
  }
  // Case 2. 删除index结点
  // step 1. 找到index前面的结点
  ListNode pre = getPrevNode(index);
  // step 2. 如果要删除的是最后一个结点，那么需要更改tail指针
  if (tail == pre.next) {
    tail = pre;
  }
  // step. 3 进行删除操作。并修改链表长度。
  pre.next = pre.next.next;
  length--;
}

代码：Java/C++/Python

总结与延伸

在本讲，我向你介绍了三板斧中的第一斧：假头，我们一起成功地设计了一个链表类，其中有 6 种基本操作——初始化、追加结点、头部插入结点、查找结点、插入指定位置前面以及删除结点。你可以参考下图：

这 6 种基本操作是学习链表的基本功，更是解决各种链表题基础的基础！你需要非常熟练地掌握！最后，设计链表完整的代码：

代码：Java/C++/Python

思考题

我再给你留一道思考题：如果在链表中进行查找的时候，给定的并不是下标，而是一个数 target，或者是一个结点 ListNode target，应该如何正确地编写这个查找函数呢？

代码：Java/C++/Python

你可以把答案写在评论区，我们一起讨论。接下来请和我一起踏上更加奇妙的算法与数据结构的旅程，继续探索解决链表问题的第二斧新链表、第三斧双指针。让我们继续前进。

下一讲将介绍 05 | 链表：如何利用“假头，新链表，双指针”解决链表题？（下）记得按时来探险。

-– ### 精选评论 ##### *中： > // step. 3 进行删除操作。并修改链表长度。 被删除的节点pre.next.next没有置为null ######     讲师回复： >     pre是删除节点的前一个节点,为了表述方便，这里我们把要删除节点标记为del，删除节点后面的那个节点设为back。我们可以把链表，表示为： pre -> del -> back 要删除的时候，只需要让链表变成pre->back就可以了(因为我们删除del这个节点) 不管那么，del == pre.next并且back = pre.next.next 如果删除del，那么只需要让pre.next = pre.next.next del.next已经被移出链表，没有必要再去处理的。当然，加上pre.next.next = null也没有什么问题。 ##### *尚： > 各种数据结构的链表都是必选课程, 但我发现其实 linux/list.h 代码是最优雅的 ##### **8831： > 这节学明白了😂 ######     编辑回复： >     很棒哦，加油～ ##### **亚： > 就是这道题完整的代码，在力扣上有个用例跑不过 ######     讲师回复： >     吓得我把手头的鸡腿扔掉，赶紧将代码：https://github.com/lagoueduCol/Algorithm-Dryad/blob/main/04.LinkedList/DesignLinkedList.java https://github.com/lagoueduCol/Algorithm-Dryad/blob/main/04.LinkedList/707.设计链表.py https://github.com/lagoueduCol/Algorithm-Dryad/blob/main/04.LinkedList/707.设计链表.cpp 都重新提交了一遍（都过了的啊），请问是哪个不过呢？(再捡起鸡腿接着吃~~) ##### **亚： > 这个完整代码好像跑不过😂 ######     讲师回复： >     吓得我把手头的鸡腿扔掉，赶紧将代码：https://github.com/lagoueduCol/Algorithm-Dryad/blob/main/04.LinkedList/DesignLinkedList.java https://github.com/lagoueduCol/Algorithm-Dryad/blob/main/04.LinkedList/707.设计链表.py https://github.com/lagoueduCol/Algorithm-Dryad/blob/main/04.LinkedList/707.设计链表.cpp 都重新提交了一遍（都过了的啊），请问是哪个不过呢？(再捡起鸡腿接着吃~~) ##### **用户7822： > 查找结点为何一前一后是Back和Front? ######     讲师回复： >     在【查找结点】这里是有动图的。链表的头在左边。指针在向右前进。你可以想象成一个人在朝右走。那么可以定义好back/front。 ##### **学： > 申请的节点是 new出来的，不需要delete吗 ######     讲师回复： >     如果是面试，必须delete ##### *超： > return getPrevNode(index).next.val; 这个返回的next是空的。 ######     讲师回复： >     老铁。我的链表是带假头的。你要取第0个结点之前的结点，我就返回dummy Head。你要取第1个结点，getPreNode()就返回第0个结点。100%是不可能为空的。请双击666 ##### **亚： > 按索引删除结点的时候，那个判断条件为什么等于length也不做操作呢 ######     讲师回复： >     因为链接表的下标是从0开始的。length表示是你有多少个元素。当你有N个元素的时候。编号是从0,1,~N-1。你肯定是不能删除第N个的 ##### *炜： > 对链表又加深了了解 ##### **方： > 动手敲代码 记笔记 ##### **5720： > 查找target，赋值current等于假头next然后while循环 ##### **6400： > 老师，请问不带假头的链表，增加节点时为什么要判断是否为空呢 ######     讲师回复： >     如果不带假头的链表，在尾部增加节点时。比如 ListNode head = null; ListNode tail = null; 要添加ListNode p = new ListNode(x); 如果我们直接tail.next = p; 由于不带假头且链表为空，这么操作直接就跪了。 需要改成 if (tail != null) { tail.next = p; } else { head = tail = p; } 这样就很烦，面试的时候一旦把这种case漏掉，就惨兮兮.