04 | 链表：如何利用“假头、新链表、双指针”解决链表题？（上）

数据结构与算法面试宝典 - 前微软资深软件工程师 - 拉勾教育

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

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

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

1. 操作链表需要非常小心，考虑各种边界情况；
2. 链表结构简单，但是查找、交换、翻转都非常容易出错；
3. 解决链表问题，需要有一定的算法思想，但是又并不太难。在面试过程中，需要你想到解题方法并实现出来，更加考察应试者的工程能力。

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

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

三板斧中的第一斧：假头

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

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

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

• 初始化
• 追加结点
• 头部插入结点
• 查找结点
• 插入指定位置之前
• 删除结点

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

class MyLinkedList {
class ListNode {
public int val = 0;
public ListNode next = null;
public ListNode() {}
public ListNode(int x) {
      val = x;
    }
  }
public MyLinkedList() {
  }
public void addAtTail(int val) {
  }
public void addAtHead(int val) {
  }
public int get(int index) {
  }
public void addAtIndex(int index, int val) {
  }
public void deleteAtIndex(int index) {
  }
}

初始化

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

private ListNode dummy = new ListNode();
private ListNode tail = dummy;
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 指针在链表发生变动的时候，就需要移动调整。

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

追加结点

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

public void addAtTail(int val) {
    tail.next = new ListNode(val);
    tail = tail.next;
    length++;
  }

代码：Java/C++/Python

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

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

• A. 需要
• B. 不需要

正确答案 B

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

头部插入结点

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

1. 新结点 p.next 指向 dummy.next；
2. dummy.next 指向 p；
3. 如果原来的 tail 指向 dummy，那么将 tail 指向 p。

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

public void addAtHead(int val) {
    ListNode p = new ListNode(val);
    p.next = dummy.next;
    dummy.next = p;
if (tail == dummy) {
      tail = p;
    }
    length++;
  }

代码：Java/C++/Python

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

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

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

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

• A. new 一个假头
• B. new 一个新结点
• C. 修改 next 指针
• D. 修改 tail 指针

正确答案 D

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

查找结点

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

好处有以下两个方面：

1. 通过 prev.next 就可以访问到你想要找到的结点，如果没有找到，那么 prev.next 为 null；
2. 通过 prev 可以方便完成后续操作，比如在 target 前面 insert 一个新结点，或者将 target 结点从链表中移出去。

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

private ListNode getPrevNode(int index) {
  ListNode front = dummy.next;
  ListNode back = dummy;
for (int i = 0; i < index && front != null; i++) {
    back = front;
    front = front.next;
  }
return back;
}

代码：Java/C++/Python

程序的执行过程如下：

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

1. 如果 target 在链表中不存在，此时 prev 返回链表的最后一个结点；
2. 如果为空链表（空链表指只有一个假头的链表），此时 prev 指向 dummy。也就是说，返回的 prev 指针总是有效的。

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

public int get(int index) {
if (index < 0 || index >= length) {
return -1;
  }
return getPrevNode(index).next.val;
}

代码：Java/C++/Python

插入指定位置之前

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

1. 如果 index 大于链表长度，则不会插入结点。
2. 如果 index 等于链表的长度，则该结点将附加到链表的末尾。
3. 如果 index 小于 0，则在头部插入结点。
4. 否则在指定位置前面插入结点。

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

• 使用 getPrevNode() 函数拿到 index 之前的结点 pre；
• 在 pre 的后面添加一个新结点。

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

public void addAtIndex(int index, int val) {
if (index > length) {
return;
  } else if (index == length) {
    addAtTail(val);
  } else if (index <= 0) {
    addAtHead(val);
  } else {
    ListNode pre = getPrevNode(index);
    ListNode p = new ListNode(val);
    p.next = pre.next;
    pre.next = p;
    length++;
  }
}

代码：Java/C++/Python

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

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

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

删除结点

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

1. 如果 index 无效，那么什么也不做；
2. 如果 index 有效，那么将这个结点删除。

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

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

public void deleteAtIndex(int index) {
if (index < 0 || index >= length) {
return;
  }
  ListNode pre = getPrevNode(index);
if (tail == pre.next) {
    tail = pre;
  }
  pre.next = pre.next.next;
  length--;
}

代码：Java/C++/Python

总结与延伸

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

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

代码：Java/C++/Python

思考题

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

代码：Java/C++/Python

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

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