关于算法:几乎刷完了力扣所有的链表题我发现了这些东西

先高低本文的提纲，这个是我用 mindmap 画的一个脑图，之后我后持续欠缺，将其余专题逐步完善起来。

大家也能够应用 vscode blink-mind 关上源文件查看，外面有一些笔记能够点开查看。源文件能够去我的公众号《力扣加加》回复脑图获取，当前脑图也会继续更新更多内容。vscode 插件地址：https://marketplace.visualstu…

大家好，我是 lucifer。明天给大家带来的专题是《链表》。很多人感觉链表是一个很难的专题。实际上，只有你把握了窍门，它并没那么难。接下来，咱们开展说说。

链表标签在 leetcode 一共有 54 道题。为了筹备这个专题，我花了几天工夫将 leetcode 简直所有的链表题目都刷了一遍。

能够看出，除了六个上锁的，其余我都刷了一遍。而实际上，这六个上锁的也没有什么难度，甚至和其余 48 道题差不多。

通过集中刷这些题，我发现了一些乏味的信息，明天就分享给大家。

<!– more –>

各种数据结构，不论是队列，栈等线性数据结构还是树，图的等非线性数据结构，从根本上底层都是数组和链表。不论你用的是数组还是链表，用的都是计算机内存，物理内存是一个个大小雷同的内存单元形成的，如图：

（图 1. 物理内存）

而数组和链表尽管用的都是物理内存，都是两者在对物理的应用上是十分不一样的，如图：

（图 2. 数组和链表的物理存储图）

不难看出，数组和链表只是应用物理内存的两种形式。

数组是间断的内存空间，通常每一个单位的大小也是固定的，因而能够按下标随机拜访。而链表则不肯定间断，因而其查找只能依附别的形式，个别咱们是通过一个叫 next 指针来遍历查找。链表其实就是一个构造体。比方一个可能的单链表的定义能够是：

interface ListNode<T> {
  data: T;
  next: ListNode;
}

data 是数据域，存放数据，next 是一个指向下一个节点的指针。

链表是一种物理存储单元上非间断、非程序的存储构造，数据元素的逻辑程序是通过链表中的指针链接秩序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点能够在运行时动静生成。

从下面的物理结构图能够看出数组是一块间断的空间，数组的每一项都是严密相连的，因而如果要执行插入和删除操作就很麻烦。对数组头部的插入和删除工夫复杂度都是 $O(N)$，而均匀复杂度也是 $O(N)$，只有对尾部的插入和删除才是 $O(1)$。简略来说”数组对查问特地敌对，对删除和增加不敌对“。为了解决这个问题，就有了链表这种数据结构。链表适宜在数据须要有肯定程序，然而又须要进行频繁增删除的场景，具体内容参考前面的《链表的基本操作》大节。

（图 3. 一个典型的链表逻辑示意图）

前面所有的图都是基于逻辑构造，而不是物理构造

链表只有一个后驱节点 next，如果是双向链表还会有一个前驱节点 pre。

有没有想过为啥只有二叉树，而没有一叉树。实际上链表就是非凡的树，即一叉树。

要想写出链表的题目，相熟链表的各种基本操作和复杂度是必须的。

插入只须要思考要插入地位前驱节点和后继节点（双向链表的状况下须要更新后继节点）即可，其余节点不受影响，因而在给定指针的状况下插入的操作工夫复杂度为O(1)。这里给定指针中的指针指的是插入地位的前驱节点。

伪代码：


temp = 待插入地位的前驱节点.next
待插入地位的前驱节点.next = 待插入指针
待插入指针.next = temp

如果没有给定指针，咱们须要先遍历找到节点，因而最坏状况下工夫复杂度为 O(N)。

提醒 1: 思考头尾指针的状况。

提醒 2: 老手举荐先画图，再写代码。等纯熟之后，天然就不须要画图了。

只须要将须要删除的节点的前驱指针的 next 指针修改为其下下个节点即可，留神思考 边界条件。

伪代码：

待删除地位的前驱节点.next = 待删除地位的前驱节点.next.next

提醒 1: 思考头尾指针的状况。

提醒 2: 老手举荐先画图，再写代码。等纯熟之后，天然就不须要画图了。

遍历比较简单，间接上伪代码。

迭代伪代码：

以后指针 =  头指针
while 以后节点不为空 {print(以后节点)
   以后指针 = 以后指针.next
}

一个前序遍历的递归的伪代码：

dfs(cur) {
    if 以后节点为空 return
    print(cur.val)
    return dfs(cur.next)
}

相熟我的小伙伴应该常常听到我说过一句话，那就是 数组和链表同样作为线性的数组构造，二者在很多不便都是雷同的，只在轻微的操作和应用场景上有差别而已。而应用场景，很难在题目中间接考查。

实际上，应用场景是能够死记硬背的。

因而，对于咱们做题来说，二者的差别通常就只是轻微的操作差别。这么说大家可能感触不够强烈，我给大家举几个例子。

数组的遍历：


for(int i = 0; i < arr.size();i++) {print(arr[i])
}

链表的遍历：

for (ListNode cur = head; cur != null; cur = cur.next) {print(cur.val)
}

是不是很像？

能够看出二者逻辑是统一的，只不过轻微操作不一样。比方：

数组是索引 ++
链表是 cur = cur.next

如果咱们须要逆序遍历呢？

for(int i = arr.size() - 1; i > - 1;i--) {print(arr[i])
}

如果是链表，通常须要借助于双向链表。而双向链表在力扣的题目很少，因而大多数你没有方法拿到前驱节点，这也是为啥很多时候会本人记录一个前驱节点 pre 的起因。

for (ListNode cur = tail; cur != null; cur = cur.pre) {print(cur.val)
}

如果往数组开端增加一个元素就是：

arr.push(1)

链表的话，很多语言没有内置的数组类型。比方力扣通常应用如下的类来模仿。

 public class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) {this.val = val;}
      ListNode(int val, ListNode next) {this.val = val; this.next = next;}
 }

咱们是不能间接调用 push 办法的。想一下，如果当你实现这个，你怎么做？你能够先本人想一下，再往下看。

3…2…1

ok，其实很简略。

// 假如 cur 是链表的尾部节点
tail.next = new ListNode('lucifer')
tail = tail.next

通过下面两行代码之后，tail 依然指向尾部节点。是不是很简略，你学会了么？

这有什么用？比方有的题目须要你复制一个新的链表，你是不是须要开拓一个新的链表头，而后一直拼接（push）复制的节点？这就用上了。

对于数组的底层也是相似的，一个可能的数组 push 底层实现：

arr.length += 1
arr[arr.length - 1] = 'lucifer'

总结一下，数组和链表逻辑上二者有很多相似之处，不同的只是一些应用场景和操作细节，对于做题来说，咱们通常更关注的是操作细节。对于细节，接下来给大家介绍，这一大节次要让大家晓得二者在思维和逻辑的 神类似。

有些小伙伴做链表题先把链表换成数组，而后用数组做，自己不举荐这种做法，这等于是否定了链表存在的价值，小朋友不要模拟。

链表题真的不难。说链表不难是有证据的。就拿 LeetCode 平台来说，处于艰难难度的题目只有两个。

其中第 23 题根本没有什么链表操作，一个惯例的“归并排序”即可搞定，而合并两个有序链表是一个简略题。如果你懂得数组的归并排序和合并两个有序链表，应该轻松拿下这道题。

合并两个有序数组也是一个简略题目，二者难度简直一样。

而对于第 25 题，置信你看完本节的内容，也能够做进去。

不过，话虽这么说，然而还是有很多小朋友给我说”指针绕来绕去就绕晕了“，”老是死循环“。。。。。。链表题目真的那么难么？咱们又该如何破解？lucifer 给大家筹备了一个口诀 一个准则，两种题型，三个留神，四个技巧，让你轻松搞定链表题，再也不怕手撕链表。咱们顺次来看下这个口诀的内容。

一个准则就是画图，尤其是对于老手来说。不论是简略题还是难题肯定要画图，这是贯通链表题目的一个准则。

画图能够缩小咱们的认知累赘，这其实和打草稿，备忘录情理是一样的，将存在脑子里的货色放到纸上。举一个不太失当的例子就是你的脑子就是 CPU，脑子的记忆就是寄存器。寄存器的容量无限，咱们须要把不那么频繁应用的货色放到内存，把寄存器用在真正该用的中央，这个内存就是纸或者电脑平板等所有你能够画图的货色。

画的难看不难看都不重要，能看清就行了。用笔轻易勾画一下，能看出关系就够了。

我把力扣的链表做了个遍。发现一个乏味的景象，那就是链表的考点很繁多。除了设计类题目，其考点无奈就两点：

指针的批改
链表的拼接

其中指针批改最典型的就是链表反转。其实链表反转不就是批改指针么？

对于数组这种反对随机拜访的数据结构来说，反转很容易，只须要头尾一直替换即可。

function reverseArray(arr) {
  let left = 0;
  let right = arr.length - 1;
  while (left < right) {const temp = arr[left];
    arr[left++] = arr[right];
    arr[right--] = temp;
  }
  return arr;
}

而对于链表来说，就没那么容易了。力扣对于反转链表的题几乎不要太多了。

明天我给大家写了一个最残缺的链表反转，当前碰到能够间接用。当然，前提是大家要先了解再去套。

接下来，我要实现的一个反转 任意一段链表

reverse(self, head: ListNode, tail: ListNode)。

其中 head 指的是须要反转的头节点，tail 是须要反转的尾节点。不难看出，如果 head 是整个链表的头，tail 是整个链表的尾，那就是反转整个链表，否则就是反转部分链表。接下来，咱们就来实现它。

首先，咱们要做的就是画图。这个我在 一个准则 局部讲过了。

如下图，是咱们须要反转的局部链表：

而咱们冀望反转之后的长这个样子：

不难看出，最终返回 tail 即可。

因为链表的递归性，实际上，咱们只有反转其中相邻的两个，剩下的采纳同样的办法实现即可。

链表是一种递归的数据结构，因而采纳递归的思维去思考往往事倍功半，对于递归思考链表将在前面《三个留神》局部开展。

对于两个节点来说，咱们只须要下批改一次指针即可，这如同不难。

cur.next = pre

就是这一个操作，不仅硬生生有了环，让你死循环。还让不应该难解难分的它们各奔前程。

对于各奔前程这个不难解决，咱们只须要反转前，记录一下下一个节点即可：

next = cur.next
cur.next = pre

cur = next

那么环呢？实际上，环不必解决。因为如何咱们是从返回后遍历，那么实际上，后面的链表曾经被反转了，因而下面我的图是错的。正确的图应该是：

至此为止，咱们能够写出如下代码：

    # 翻转一个子链表，并返回新的头与尾
    def reverse(self, head: ListNode, tail: ListNode):
        cur = head
        pre = None
        while cur != tail:
            # 留下联系方式
            next = cur.next
            # 批改指针
            cur.next = pre
            # 持续往下走
            pre = cur
            cur = next
        # 反转后的新的头尾节点返回进来
        return tail, head

如果你仔细观察，会发现，咱们的 tail 实际上是没有被反转的。解决办法很简略，将 tail 前面的节点作为参数传进来呗。

class Solution:
    # 翻转一个子链表，并且返回新的头与尾
    def reverse(self, head: ListNode, tail: ListNode, terminal:ListNode):
        cur = head
        pre = None
        while cur != terminal:
            # 留下联系方式
            next = cur.next
            # 批改指针
            cur.next = pre

            # 持续往下走
            pre = cur
            cur = next
         # 反转后的新的头尾节点返回进来
        return tail, head

置信你对反转链表曾经有了肯定的理解。前面咱们还会对这个问题做更具体的解说，大家先留个印象就好。

大家有没有发现链表总喜爱穿来穿去（拼接）的？比方反转链表 II，再比方合并有序链表等。

为啥链表总喜爱穿来穿去呢？实际上，这就是链表存在的价值，这就是设计它的初衷呀！

链表的价值就在于其 不用要求物理内存的连续性，以及对插入和删除的敌对。这在文章结尾的链表和数组的物理结构图就能看进去。

因而链表的题目很多拼接的操作。如果下面我讲的链表基本操作你会了，我置信这难不倒你。除了环，边界等。。。^\_^。这几个问题咱们前面再看。

链表最容易出错的中央就是咱们应该留神的中央。链表最容易出的错 90 % 集中在以下三种状况：

呈现了环，造成死循环。
分不清边界，导致边界条件出错。
搞不懂递归怎么做

接下来，咱们一一来看。

环的考点有两个：

题目就有可能环，让你判断是否有环，以及环的地位。
题目链表没环，然而被你操作指针整出环了。

这里咱们只探讨第二种，而第一种能够用咱们前面提到的 快慢指针算法。

避免出现环最简略无效的措施就是画图，如果两个或者几个链表节点形成了环，通过图是很容易看进去的。因而一个简略的 实操技巧就是先画图，而后对指针的操作都反馈在图中。

然而链表那么长，我不可能全副画进去呀。其实齐全不必，下面提到了链表是递归的数据结构，很多链表问题天生具备递归性，比方反转链表，因而 仅仅画出一个子结构就能够了。这个常识，咱们放在前面的 前后序 局部解说。

很多人错的是没有思考边界。一个思考边界的技巧就是看题目信息。

如果题目的头节点可能被移除，那么思考应用虚构节点，这样 头节点就变成了两头节点，就不须要为头节点做非凡判断了。
题目让你返回的不是本来的头节点，而是尾部节点或者其余两头节点，这个时候要留神指针的变动。

以上两者局部的具体内容，咱们在略微讲到的虚构头局部解说。老规矩，大家留个印象即可。

ok，是时候填坑了。下面提到了链表构造天生具备递归性，那么应用递归的解法或者递归的思维都会对咱们解题有帮忙。

在二叉树遍历局部，我讲了二叉树的三种风行的遍历办法，别离是前序遍历，中序遍历和后序遍历。

前中后序实际上是指的以后节点绝对子节点的解决程序。如果先解决以后节点再解决子节点，那么就是前序。如果先解决左节点，再解决以后节点，最初解决右节点，就是中序遍历。后序遍历天然是最初解决以后节点了。

理论过程中，咱们不会这么扣的这么死。比方：

def traverse(root):
    print('pre')
    traverse(root.left)
    traverse(root.righ)
    print('post')

如上代码，咱们既在 进入左右节点前 有逻辑，又在 退出左右节点之后 有逻辑。这算什么遍历形式呢？个别意义上，我习惯只看主逻辑的地位，如果你的主逻辑是在前面就是后序遍历，主逻辑在后面就是前序遍历。这个不是重点，对咱们解题帮忙不大，对咱们解题帮忙大的是接下来要讲的内容。

绝大多数的题目都是单链表，而单链表只有一个后继指针。因而只有前序和后序，没有中序遍历。

还是以下面讲的经典的反转链表来说。如果是前序遍历，咱们的代码是这样的：

def dfs(head, pre):
    if not head: return pre
    next = head.next
    # # 主逻辑（扭转指针）在前面
    head.next = pre
    dfs(next, head)

dfs(head, None)

后续遍历的代码是这样的：


def dfs(head):
    if not head or not head.next: return head
    res = dfs(head.next)
    # 主逻辑（扭转指针）在进入前面的节点的前面，也就是递归返回的过程会执行到
    head.next.next = head
    head.next = None

    return res

能够看出，这两种写法不论是边界，入参，还是代码都不太一样。为什么会有这样的差别呢？

答复这个问题也不难，大家只有记住一个很简略的一句话就好了，那就是 如果是前序遍历，那么你能够设想后面的链表都解决好了，怎么解决的不必管 。相应地 如果是后续遍历，那么你能够设想前面的链表都解决好了，怎么解决的不必管。这句话的正确性也是毋庸置疑。

如下图，是前序遍历的时候，咱们应该画的图。大家把注意力集中在两头的框（子结构）就行了，同时留神两点。

后面的曾经解决好了
前面的还没解决好

据此，咱们不难写出以下递归代码，代码正文很具体，大家看正文就好了。

def dfs(head, pre):
    if not head: return pre
    # 留下联系方式（因为前面的都没解决，因而能够通过 head.next 定位到下一个）next = head.next
    # 主逻辑（扭转指针）在进入前面节点的后面（因为后面的都曾经解决好了，因而不会有环）head.next = pre
    dfs(next, head)

dfs(head, None)

如果是后序遍历呢？老规矩，秉承咱们的一个准则，先画图。

不难看出，咱们能够通过 head.next 拿到下一个元素，而后将下一个元素的 next 指向本身来实现反转。

用代码示意就是:

head.next.next = head

画出图之后，是不是很容易看出图中有一个环？当初晓得画图的益处了吧？就是这么直观，当你很纯熟了，就不须要画了，然而在此之前，请不要偷懒。

因而咱们须要将 head.next 改为不会造成环的一个值，比方置空。

def dfs(head):
    if not head or not head.next: return head
    # 不须要留联系方式了，因为咱们前面曾经走过了，不需走了，当初咱们要回去了。res = dfs(head.next)
    # 主逻辑（扭转指针）在进入前面的节点的前面，也就是递归返回的过程会执行到
    head.next.next = head
    # 置空，避免环的产生
    head.next = None

    return res

值得注意的是，前序遍历很容易革新成迭代，因而举荐大家应用前序遍历。我拿下面的迭代和这里的前序遍历给大家比照一下。

那么为什么 前序遍历很容易革新成迭代 呢？实际上，这句话我说的不精确，精确地说应该是 前序遍历容易改成不须要栈的递归，而后续遍历须要借助栈来实现。这也不难理解，因为后续遍历的主逻辑在函数调用栈的弹出过程，而前序遍历则不须要。

这里给大家插播一个写递归的技巧，那就是设想咱们曾经解决好了一部分数据，并把他们用手挡起来，然而还有一部分期待解决，接下来思考”如何依据曾经解决的数据和以后的数据来推导还没有解决的数据“就行了。

针对下面的考点和留神点，我总结了四个技巧来应答，这都是在平时做题中十分实用的技巧。

来理解虚构头的意义之前，先给大家做几个小测验。

Q1: 如下代码 ans.next 指向什么？

ans = ListNode(1)
ans.next = head
head = head.next
head = head.next

A1: 最开始的 head。

Q2：如下代码 ans.next 指向什么？

ans = ListNode(1)
head = ans
head.next = ListNode(3)
head.next = ListNode(4)

A2: ListNode(4)

仿佛也不难，咱们持续看一道题。

Q3: 如下代码 ans.next 指向什么？

ans = ListNode(1)
head = ans
head.next = ListNode(3)
head = ListNode(2)
head.next = ListNode(4)

A3: ListNode(3)

如果三道题你都答对了，那么祝贺你，这一部分能够跳过。

如果你没有懂也没关系，我这里简略解释一下你就懂了。

ans.next 指向什么取决于最初切断 ans.next 指向的中央在哪。比方 Q1，ans.next 指向的是 head，咱们假如其指向的内存编号为 9527。

之后执行 head = head.next（ans 和 head 被切断分割了），此时的内存图：

咱们假如头节点的 next 指针指向的节点的内存地址为 10200

不难看出，ans 没变。

对于第二个例子。一开始和下面例子一样，都是指向 9527。而后执行了：

head.next = ListNode(3)
head.next = ListNode(4)

ans 和 head 又同时指向 ListNode(3) 了。如图：

head.next = ListNode(4) 也是同理。因而最终的指向 ans.next 是 ListNode(4)。

咱们来看最初一个。前半部分和 Q2 是一样的。

ans = ListNode(1)
head = ans
head.next = ListNode(3)

依照下面的剖析，此时 head 和 ans 的 next 都指向 ListNode(3)。要害是上面两行：

head = ListNode(2)
head.next = ListNode(4)

指向了 head = ListNode(2) 之后，head 和 ans 的关系就被切断了，以后以及之后所有的 head 操作都不会影响到 ans，因而 ans 还指向被切断前的节点，因而 ans.next 输入的是 ListNode(3)。

花了这么大的篇幅讲这个货色的起因就是，指针操作是链表的外围，如果这些根底不懂，那么就很难做。接下来，咱们介绍配角 – 虚构头。

置信做过链表的小伙伴都听过这么个名字。为什么它这么好用？它的作用无非就两个：

将头节点变成两头节点，简化判断。
通过在适合的时候断开链接，返回链表的两头节点。

我下面提到了链表的三个留神，有一个是边界。头节点是最常见的边界，那如果 咱们用一个虚构头指向头节点，虚构头就是新的头节点了，而虚构头不是题目给的节点，不参加运算，因而不须要非凡判断，虚构头就是这个作用。

如果题目须要返回链表两头的某个节点呢？实际上也可借助虚构节点。因为我下面提到的指针的操作，实际上，你能够新建一个虚构头，而后让虚构头在失当的时候（刚好指向须要返回的节点）断开连接，这样咱们就能够返回虚构头的 next 就 ok 了。25. K 个一组翻转链表就用到了这个技巧。

不仅仅是链表，二叉树等也常常用到这个技巧。比方我让你返回二叉树的最左下方的节点怎么做？咱们也能够利用下面提到的技巧。新建一个虚构节点，虚构节点 next 指向以后节点，并跟着一起走，在递归到最左下的时候断开链接，最初返回虚构节点的 next 指针即可。

判断链表是否有环，以及环的入口都是应用快慢指针即可解决。这种题就是不晓得不会，晓得了就不容易忘。不多说了，大家能够参考我之前的题解 https://github.com/azl3979858…。

除了这个，求链表的交点也是快慢指针，算法也是相似的。不这都属于不晓得就难，晓得了就容易。且下次写不容易想不到或者出错。

这部分大家参考我下面的题解理一下，写一道题就能够把握。接下来，咱们来看下 穿针引线 大法。

另外因为链表不反对随机拜访，因而如果想要获取数组两头项和倒数第几项等特定元素就须要一些非凡的伎俩，而这个伎俩就是快慢指针。比方要找链表两头项就 搞两个指针，一个大步走（一次走两步），一个小步走（一次走一步），这样快指针走到头，慢指针刚好在两头。如果要求链表倒数第 2 个，那就 让快指针先走一步，慢指针再走 ，这样快指针走到头，慢指针刚好在倒数第二个。这个原理不难理解吧？这种技巧属于 会了就容易，且不容易忘。不会就很难想出的类型，因而大家学会了拿几道题练一下就能够放下了。

这是链表的第二个考点 – 拼接链表。我在 25. K 个一组翻转链表，61. 旋转链表和 92. 反转链表 II 都用了这个办法。穿针引线是我本人起的一个名字，起名字的益处就是不便记忆。

这个办法通常不是最优解，然而好了解，不便书写，不易出错，举荐老手用。

还是以反转链表为例，只不过这次是 反转链表的两头一部分，那咱们该怎么做？

反转后面咱们曾经讲过了，于是我假如链表曾经反转好了，那么如何将反转好的链表拼后去呢？

咱们想要的成果是这样的：

那怎么达到图上的成果呢？我的做法是从做到右给断点编号。如图有两个断点，共波及到四个节点。于是我给它们顺次编号为 a，b，c，d。

其实 a，d 别离是须要反转的链表局部的前驱和后继（不参加反转），而 b 和 c 是须要反转的局部的头和尾（参加反转）。

因而除了 cur，多用两个指针 pre 和 next 即可找到 a，b，c，d。

找到后就简略了，间接 穿针引线。

a.next = c
b.next = d

这不就好了么？我记得的就有 25 题，61 题和 92 题都是这么做的，清晰不凌乱。

这是四个技巧的最初一个技巧了。尽管是最初讲，但并不意味着它不重要。相同，它的实操价值很大。

持续回到下面讲的链表反转题。

cur = head
pre = None
while cur != tail:
    # 留下联系方式
    next = cur.next
    # 批改指针
    cur.next = pre
    # 持续往下走
    pre = cur
    cur = next
# 反转后的新的头尾节点返回进来

什么时候须要判断 next 是否存在，下面两行代码先写哪个呢？

是这样？

    next = cur.next
    cur.next = pre

还是这样？

    cur.next = pre
    next = cur.next

我给你的倡议是：先穿。这里的穿是批改指针，包含反转链表的批改指针和穿针引线的批改指针。先别管程序，先穿。

穿完之后，代码的总数曾经确定了，无非就是排列组合让代码没有 bug。

因而第二步思考程序，那下面的两行代码哪个在前？应该是先 next = cur.next，起因在于后一条语句执行后 cur.next 就变了。因为下面代码的作用是反转，那么其实通过 cur.next = pre 之后链表就断开了，前面的都拜访不到了，也就是说此时你 只能返回头节点这一个节点。

实际上，有如果有十行穿的代码，咱们很多时候没有必要全思考。咱们 须要思考的仅仅是被扭转 next 指针的局部。比方 cur.next = pre 的 cur 被改了 next。因而上面用到了 cur.next 的中央就要思考放哪。其余代码不须要思考。

和下面的准则相似，穿完之后，代码的总数曾经确定了，无非就是看看哪行代码会空指针异样。

和下面的技巧一样，咱们很多时候没有必要全思考。咱们 须要思考的仅仅是被扭转 next 指针的局部。

比方这样的代码


while cur:
    cur = cur.next

咱们思考 cur 是否为空呢？很显著不可能，因为 while 条件保障了，因而不需判空。

那如何是这样的代码呢？

while cur:
    next = cur.next
    n_next = next.next

如上代码有两个 next，第一个不必判空，下面曾经讲了。而第二个是须要的，因为 next 可能是 null。如果 next 是 null，就会引发空指针异样。因而须要批改为相似这样的代码：

while cur:
    next = cur.next
    if not next: break
    n_next = next.next

以上就是咱们给大家的四个技巧了。置信有了这四个技巧，写链表题就没那么艰巨啦~ ^\_^

最初举荐几道题给大家，用明天学到的常识解决它们吧~

21. 合并两个有序链表
82. 删除排序链表中的反复元素 II
83. 删除排序链表中的反复元素
86. 分隔链表
92. 反转链表 II
138. 复制带随机指针的链表
141. 环形链表
142. 环形链表 II
143. 重排链表
148. 排序链表
206. 反转链表
234. 回文链表

数组和栈从逻辑上没有大的区别，你看基本操作都是差不多的。如果是单链表，咱们无奈在 $O(1)$ 的工夫拿到前驱节点，这也是为什么咱们遍历的时候老是保护一个前驱节点的起因。然而实质起因其实是链表的增删操作都依赖前驱节点。这是链表的基本操作，是链表的个性天生决定的。

可能有的同学有这样的疑难”考点你只讲了指针的批改和链表拼接，难道说链表就只会这些就够了？那我做的题怎么还须要我会前缀和啥的呢？你是不是坑我呢？“

我后面说了，所有的数据结构底层都是数组和链表中的一种或两种。而咱们这里讲的链表指的是考查链表的基本操作的题目。因而如果题目中须要你应用归并排序去合并链表，那其实归并排序这部分曾经不再本文的探讨范畴了。

实际上，你去力扣或者其余 OJ 翻链表题会发现他们的链表题大都指的是入参是链表，且你须要对链表进行一些操作的题目。再比方树的题目大多数是入参是树，你须要在树上进行搜寻的题目。也就是说须要操作树（比方批改树的指针）的题目很少，比方有一道题让你给树减少一个 right 指针，指向同级的右侧指针，如果曾经是最右侧了，则指向空。

链表的基本操作就是增删查，牢记链表的基本操作和复杂度是解决问题的根本。有了这些根本还不够，大家要牢记我的口诀”一个准则，两个考点，三个留神，四个技巧“。

做链表的题，要想入门，无它，唯画图尔。能画出图，并依据图进行操作你就入门了，甭管你写的代码有没有 bug。

而链表的题目外围的考察点只有两个，一个是指针操作，典型的就是反转。另外一个是链表的拼接。这两个既是链表的精华，也是次要考点。

晓得了考点必定不够，咱们写代码哪些地方容易犯错？要留神什么？这里我列举了三个容易犯错的中央，别离是环，边界和前后序。

其中环指的是节点之间的互相援用，环的题目如果题目自身就有环，90 % 双指针能够解决，如果自身没有环，那么环就是咱们操作指针的时候留下的。如何解决呈现环的问题？那就是 画图，而后聚焦子结构，疏忽其余信息。

除了环，另外一个容易犯错的中央往往是边界的条件，而边界这块链表头的判断又是一个大头。克服这点，咱们须要认真读题，看题目的要求以及返回值，另外一个很有用的技巧是虚构节点。

如果大家用递归去解链表的题，肯定要留神本人写的是前序还是后序。

如果是前序，那么 只思考子结构即可，后面的曾经解决好了，怎么解决的，不必管。非要问，那就是同样办法。前面的也不需思考如何解决，非要问，那就是用同样办法
如果是后续，那么 只思考子结构即可，前面的曾经解决好了，怎么解决的，不必管。非要问，那就是同样办法。后面的不需思考如何解决。非要问，那就是用同样办法

如果你想递归和迭代都写，我举荐你用前序遍历。因为前序遍历容易改成不必栈的递归。

以上就是链表专题的全部内容了。大家对此有何认识，欢送给我留言，我有工夫都会一一查看答复。更多算法套路能够拜访我的 LeetCode 题解仓库：https://github.com/azl3979858…。目前曾经 37K star 啦。大家也能够关注我的公众号《力扣加加》带你啃下算法这块硬骨头。

我整顿的 1000 多页的电子书曾经开发下载了，大家能够去我的公众号《力扣加加》后盾回复电子书获取。

关于算法:几乎刷完了力扣所有的链表题我发现了这些东西

简介

链表的基本操作

插入

删除

遍历

链表和数组到底有多大的差别？

链表题难度几何？

一个准则

两个考点

指针的批改

链表的拼接

三个留神

环

边界

前后序

四个技巧

虚构头

快慢指针

穿针引线

先穿再排后判空

先穿

再排

后判空

题目举荐

总结