[LeetCode] 专题总结——链表刷题指南

0. 写在前面的话

做题之后的整理与总结，和做题本身同样重要。

目前为止，LeetCode上标签为 “Linked List” 的题目共计35道，排在最后面的是第1019题。在这35道题目中，有5道题是需要解锁才可以做的。剩余的30题，我都做完了。

下面，我会把这30道题做一个详细的整理。

1. 基本介绍

链表是一种根据元素逻辑结果排列起来的数据结构，和数组比较像。但是这两者的区别在于，数组的长度是固定的，而链表的长度是不确定的。在现实情况中，需要保存的元素长度往往是不固定的，此时就可以使用链表进行存储。

在每个节点中，主要保存的属性是数据（data）和下一个节点的引用（next）。
在进行链表操作的时候，首先需要的是一个根节点（第一个节点即为根节点），然后每一个节点的引用都保存在上一节点的next属性中。而在进行输出的时候也应该按照节点的先后顺序，一个一个取得每一个节点所包含的数据。

2. 主要技巧

2.1 使用辅助头节点

当链表原来的头节点可能会被改变的时候，我们往往会使用一个伪节点放在链表的最前面，方便遍历链表、返回正确的结果。这个伪节点就是辅助头节点。
什么时候用辅助头节点，什么时候不用呢？
当头结点可能被反转、删除、改变时，或者头节点不存在（链表为空）时，就需要使用辅助头节点，便于返回正确的结果。

对应题目：
19. Remove Nth Node From End of List
删除链表中倒数第 n 个元素。原来的头节点可能被删除掉，所以需要使用辅助头节点。
203. Remove Linked List Elements
删除链表中所有元素值为 val 的节点。原来的头节点可能被删除掉，所以需要使用辅助头节点。

2.2 反转一个单向链表

反转一个链表有很多方法，比较推荐的方法是改变节点的 next 指针。将每个节点的 next 指针修改为指向前一个元素。这样就完成了一个链表的反转。

对应题目：
206. Reverse Linked List
反转一个单向链表，建议熟练掌握。反转链表是解决一些题目的重要步骤，如果这一步骤都不会，就无法做出来整个题目了。

2.3 双指针法

双指针法是一种非常常见的方法，强烈建议熟练掌握。这个方法也很灵活，可以做很多事情。在链表中可以用来确定固定的长度的位置、寻找链表的中点、将链表一分为二等等。

对应题目：
19. Remove Nth Node