看动画，拿 Offer：大厂算法面试真题全解析

添加社群管理员：微信号【】

订阅福利 订阅后，分享专属海报，每邀请一位好友订阅有奖励。免费获取价值 800 元大礼包最新课表抢先看，订阅会员更优惠。找客服要优惠：微信号【】 链表逆序（ 206）

今天讲解的题目选自 206 链表逆序

题目

已知一个单链表，头结点指针为 head，我们需要将 head 指向的链表进行逆序，并返回逆序后的头结点地址。

例如，链表中存储了 1、2、3、4、5 这 5 个结点，逆序后变为 5、4、3、2、1，此时头结点中存储了 5，将它返回。

输入: 1->2->3->4->5->NULL输出: 5->4->3->2->1->NULL

这里我们要注意，解决该问题需要在原链表上进行相关操作，不可以申请类似数组的额外内存空间，保证空间复杂度为 O(1)。

题目中节点的数据结构 ，代表链表中的一个节点，val 是节点中存储的数据，next 是指向下一个节点的指针，构造函数 初始化 val 的值为 x，next 赋为空。

我们需要实现 函数，函数传入原链表的头结点指针 head，返回逆置后的新链表头结点地址。例如， 输入链表 1、2、3、4、5，返回逆置后链表头结点 5 的地址。

我们首先思考如何将链表一个结点一个结点的逆置。

先看一段打印链表的代码，，函数传入两个参数，链表的头结点指针 head 和链表的名字 name。在函数中，打印字符串 name。然后判断 head 是否为空，如果 head 为空，打印 NULL，并返回。如果 head 不空，遍历并打印链表的每一个节点值。

接着我们开发主程序，首先构造 5 个结点 a、b、c、d、e，并将它们初始化为 1、2、3、4、5，通过结点的 next 指针域，将 a、b、c、d、e 这 5 个结点依次连接在一起。

下面我们来研究如何将链表一个结点一个结点的逆置。

设置 head 指向链表的头结点 a，设置 为新链表头结点指针，最初指向空。

设置指针 next，初始化为空，后面 next 用来备份当前操作结点的下一个结点的地址。

我们调用 函数，打印出当前 head 与 指向的链表。我们发现旧链表打印结果为 1、2、3、4、5， 新链表打印结果为 NULL。

然后对第一个结点逆置，逆置结点包括 4 个步骤。

首先通过代码 next = head->next (读作 next 等于 head next)，备份 head 的下一个结点的地址。

然后通过代码 head->next = 将 head 的指针域赋值为 ，即将第 1 个结点与原链表断开，使它指向新链表的头结点。

接下来把 指向新链表的头结点，通过代码 = head，将 赋值为 head。

最后通过代码 head = next，将 head 指向当前原链表的头结点。

至此，我们完成了一个节点的逆置。调用 打印出原链表与新链表，head 对应的原链表为 2、3、4、5， 对应的新链表为 1。

我们再来看第二个结点的逆置。和第一个节点逆置的过程相同，首先通过代码 next = head->next，备份 head 指针的下一个节点地址，将它存储至 next 中。

然后通过代码 head->next = ，将第 2 个结点与原链表断开，使它指向新链表的头结点。

再通过代码 = head，将 指向新链表的头结点。

最后通过代码 head = next，将 head 指向当前原链表的头结点。

然后完成了第 2 个节点的逆置。调用 打印出原链表与新链表，head 对应的原链表为 3、4、5， 对应的新链表为 1、2。

对于第 3、4、5 个节点的逆置，我们开发相同的 3 组代码，在逆置过程中，可以通过 打印节点变化，原链表从 3、4、5 变为 4、5，再到 5，最终为 NULL；新链表从 2、1 变为 3、2、1，再到 4、3、2、1，最终为 5、4、3、2、1。

我们可以发现，每次逆置结点时的指针操作代码是完全一样的，所以可以通过循环来代替这些重复操作。

整体代码如下，首先构造 5 个结点 a、b、c、d、e，使用 next 指针将它们连接在一起。

将 head 指向链表的第一个结点 a，设置 与 next 指针，并赋值为空，然后打印原链表与新链表，原始链表为 1、2、3、4、5，新链表为空。

利用 for 循环重复 5 次逆置操作的代码，每次操作与逆置某一个结点的代码一样，即 4 个步骤：

代码 next = head->next，备份 head 指针的下一个结点；head->next = ，将 head 指向的结点与新链表的头结点连接； = head，将 指向新链表头结点，赋值为 head；head = next，将 head 指向 next 指向的结点，即当前原链表的头结点。

然后打印两个链表，我们看到 head 指向的原始链表从 1、2、3、4、5 变为 2、3、4、5，然后是 3、4、5 等等，最后变为 NULL。 指向的新链表从 NULL，变为 1，然后是 2、1 等等，最后变为 5、4、3、2、1。

我们刚刚通过 for 循环逆置了一个五个结点的链表，而在本题中我们并不知道链表结点的个数，题目需要开发的接口 只传入了链表的头指针 head。虽然我们可以通过循环来统计链表的结点个数，然后再通过 for 循环逆置链表，但这样做未免显得有些笨拙。

所以我们将 for 循环修改为 while 循环，while 循环的条件是判断 head 指针是否为空，当 head 为空时，原链表即完成了全部结点的逆置，而循环内的代码是完全一样的，这就是更通用的链表逆置方法，直接逆置法。

至此，方法 1 就讲完了。

除了直接逆置法，我们来看另一种方法，头插法。

头插法需要设置一个额外的临时头结点 temp，这里要特别注意，temp 不是一个指针，而是一个结点。

头插法利用 head 指针遍历原链表，每遍历一个结点，即将 head 访问的结点插入 temp 结点后。当所有的结点都插入到 temp 结点后时，head 指向空，temp 结点的 next 指针即指向逆置后的新链表。

我们来看头插法完整的运行过程，初始状态 head 指向的链表为 1、2、3、4、5，temp 头结点后面没有结点，将此时 head 指向的结点插入到 temp 结点后，原始链表变为 2、3、4、5，temp 结点后的链表为 1；然后将结点 2 插入到 temp 的后面，原始链表变为 3、4、5，新链表变为 2、1；随着 head 指针遍历原始链表，原始链表上的所有结点都被插入到 结点的后面，最终 head 指针指向空，temp 结点后的链表为 5、4、3、2、1。而 temp.next 指向的地址即为新链表的第一个结点，我们将它返回。

头插法在处理某个结点的指针修改时，与直接逆置法一样，以处理第 3 个结点为例，此时 head 指向的链表为 3、4、5，temp 结点后的链表为 2、1。

首先通过代码 next = head->next 备份 head 指针的下一个节点，即将 4 号结点的地址存储在 next 指针中。

然后修改 head 指向结点的 next 指针, 通过代码 head->next = temp.next 使其指向临时头结点的下一个结点。即将 3 号结点指向 temp 结点后的 2 号结点。

完成 head 的 next 指针修改后，通过代码 temp.next = head；修改临时头结点 temp 的 next 指针, 使 temp 指向 head 指向的结点。这样就把 3 号结点插入到临时头结点的后面了。

最后移动 head 指针，通过代码 head = next；使 head 指向 next 备份的地址，即原链表的 4 号结点。这样就完成了头插法逆置 3 号节点。

来看头插法的实现代码， 函数，传入 head 指针，指向待逆置链表。

首先设置临时头结点 temp，通过 while 循环逆置链表，在循环内部，代码 next = head->next，备份 head 指针的下一个结点；代码 head->next = temp.next，修改 head 指向的节点，使其指向临时头结点 temp 的下一个结点。

代码 temp.next = head，使临时头结点 temp 指向 head 指向的结点。

代码 head = next，移动 head 指针，将其指向 next 备份的地址。

最终返回临时头结点的下一个节点地址 temp.next，即逆置后的链表头结点。

我们来对比一下这两种方法，两种方法的不同点是思考角度不同，逆置法通过指针的操作进行链表结点的原地逆置，头插法通过引入临时头结点将原链表的结点插入至该结点后。

这两种代码背后含义是相同的，具体来说，首先设置临时头结点 temp 与逆置指针 ；通过代码 next = head->next;对 head 指针的下一个结点地址备份。

然后修改 head 指向节点的 next 域，使其指向新链表的第一个结点，代码分别是 head->next = 与 head->next = temp.next，这里要注意，我们并没有使用到 temp 节点的 val 域，而 与 temp.next 都只是存储新链表第一个结点地址的指针。

完成修改后，移动存储新链表第一个结点的指针， 与 temp.next，将它指向 head；最后，将 head 赋值为 next 指向的结点地址，继续处理下一个结点。以上就是逆置法与头插法的相同点与不同点。

最后我们开发一个 main 函数测试一下程序接口，程序设置 a、b、c、d、e 五个节点，通过 next 指针将它们连接。调用 将链表进行逆置，并通过 函数打印逆置前后的链表。最后提交 ，题目通过测试。 206 链表逆序这道题目就讲完了。

链表求交点（ 160）

今天讲解的题目选自 160 链表求交点

题目

已知两个链表，指针 headA 指向链表 A 的头节点，headB 指向链表 B 的头节点。如果这两个链表相交，找到两个链表相交的节点，返回该节点地址。

例如，链表 A 和链表 B 相交于 C 结点，我们返回 C 节点的地址。如果两个链表之间没有交点，程序返回 null。

我们要注意，求解交点的过程中，链表需要保持原有的数据和结构，即不能删除节点，添加节点或是改变节点内的数据。

另外，本题有多种解法。实现算法时，应尽量使算法的时间复杂度为 O(n)，空间复杂度为 O(1) 。

来看一个例子，链表 A 为 4、1、8、4、5，链表 B 为 5、0、1、8、4、6。两个链表此时相交于值为 8 的节点，我们应将该节点的地址返回。

题目中节点的数据结构 ，代表链表中的一个节点，val 是节点中存储的数据，next 是指向下一个节点的指针，构造函数 初始化 val 的值为 x，next 赋为空。

我们需要开发求两个链表，交点的函数 ，函数传入两个链表的头结点指针 headA 与 headB。如果两个链表有交点，函数返回相交节点的地址，否则返回 NULL。

我们来分析一下这个题目。

首先可以想到两层循环来直接求解该问题，用 headA 遍历链表 A，对 A 中的每一个节点使用 headB 遍历 B 中的每个节点，并同时检查 headB 是否与 headA 相同。如果相同，说明找到了两个链表的交点。

例如，最初 headA 指向 A 的第一个节点，通过 headB 遍历 B 中的节点时并没有发现地址与 headA 相同的节点。然后我们向后移动 headA，在链表 B 中，同样没有找到地址相同的节点。

当 headA 指向第 3 个节点时，使用 headB 遍历链表 B 中的节点找到了与 headA 地址相同节点即两链表的交点，此时将它返回即可。

如果两个链表没有交点，最终 headA 于 headB 均会指向 NULL，程序返回 NULL。

假设链表 A、B 长度为 n，该方法的时间复杂度为 O(n^2)，并不是理想的方法。

我们再介绍两个更优的算法。

第一种方法，通过 STL 中的 set 来优化搜索相同地址的过程。

首先构建一个空的 set。然后遍历链表 A，将 A 中每个节点的地址插入到 set 中。例如将地址 0x00A、0x00B、0x00C 等，添加至 set 再遍历链表 B，将 B 中每个节点的地址在 set 中进行查询。当遇到第一个 set 中已出现的地址时，即找到了两个链表的交点，否则两个链表没有交点。

例如遍历至节点 8 时，发现它的地址 0x00C 已经在 set 中出现，那么该节点为两个链表的交点，我们将它的地址返回。如果遍历了链表 B 中的全部节点，没有找到在 set 中出现过的地址，则说明链表中没有环。

在正式讲解题目代码之前，我们先看一下 set 容器的使用。

样例代码利用 STL set 找出数组 a 与 b 中同时出现的元素，首先需要# 引用 set 类的头文件。在 main 函数中，创建命名为 的 set 和数组 a、b。首先遍历数组 a，将 a 中的元素添加至 ，然后遍历数组 b，检查 b 中的元素是否在 中出现。如果 中出现过该元素，则将它打印至屏幕，最终我们得到 a 与 b 中同时出现的元素为 5、1、8、4、5。

然后我们来讲解该方法的代码实现。

首先，设置用来判断相同节点的集合 ，指针 存储两链表的交点，初始化为 NULL。使用 while 循环遍历链表 A 将链表 A 中的节点地址添加至 ，然后遍历链表 B，通过代码 .find(headB) != .end()判断节点是否在 中出现。如果 if 条件成立，说明找到了重复的节点，而第一个重复的节点即为链表相交的交点将它存储至 ，跳出循环，最终函数返回 。

至此，方法 1 的思路与实现就讲完了。利用 set 来判断重复的地址时，由于 set 利用红黑树实现，在 set 集合中查找与添加一个元素的时间复杂度为 O(logN)。所以算法的整体时间复杂度是 O(NlogN)，由于我们需要把所有的地址都通过 set 存储，所以空间复杂度为 O(N)。

下面我们介绍双指针计算法。

使得时间复杂度优化为 O(N)，空间复杂度优化为 O(1)。我们发现，在两个链表相交后，有一段共享的链表，并且长链表比短链表多出一些结点。在找相交节点的时候，可以首先排除掉长链表多出的结点，这时两个链表的长度就相同了。

然后再通过两个指针同时用相同速度扫描两个链表，当找到同一个节点时即为两个链表的交点了。

具体来说，首先通过指针遍历链表，计算链表 A 和链表 B 的长度，相减得出较长的链表多出的节点个数 count。例如，链表 A 的长度为 5，链表 B 的长度为 6，链表 B 比链表 A 多出了 1 个节点，然后将较长链表的头结点指针向前移动 count 个节点，也就是将较长链表指针移动到和较短链表头结点对齐的位置。

例如，计算出长链表比短链表多出 1 个节点，所以将 headB 向后移动 1 个节点，最后将 headA 与 headB 同时向前移动，当两指针指向同一个节点时，就找到了两链表的相交节点，将该节点地址返回，如果没有交点则返回 NULL。

例如，当 headA 与 headB 移动到节点 8 时，两个指针值相同，即找到了两个链表的相交节点，我们将该地址返回。

首先开发计算链表的长度 函数。

函数参数为待求长度的链表头结点指针 head，设置 存储链表长度，通过 while 循环，每遍历一个节点，++，最后函数返回链表的长度 ，然后开发，移动较长链表头结点指针的函数 ，函数传入链表头结点指针 head 与移动的节点数 count，通过 for 循环，将 head 指针向前移动 count 个节点，函数返回移动后的指针 head。

最后来看 主体代码的开发。

首先计算链表 A 与链表 B 的长度，分别存储至 与 。然后使用 if 语句比较 与 的大小，通过 函数，移动较长链表的头结点，使指针 headA 与 headB 对齐，最后求两个链表的交点，设置 存储交点地址。通过 while 循环，同时向前移动 headA 与 headB，当 headA 与 headB 相等时，该节点即为两链表的交点，将它的地址存储至 ，并跳出循环，函数最终返回 ，两个链表的交点地址。

最后我们开发 main 函数测试程序接口。程序中设置了样例中的 8 个节点 a、b、c、d、e、f、g、h，链表 a、b 与链表 c、d、e 相交于节点 f，调用函数 ，求出两链表的交点地址。

提交 ，题目通过测试， 160 相交链表这道题目就讲完了。

两个排序链表的合并（ 21）链表划分（ 86）链表中的环的入口节点（ 142）使用栈实现队列 （ 232）包含 min 函数的栈 （ 155）合法的出栈序列（ 946）分糖果 （ 455）射击气球（ 452）移除 K 个数字 （ 402）跳跃游戏（ 55）求子集 （ 78）生成括号（ 22）N 皇后 （ 51）火柴棍摆正方形（ 473）路径总和 II （ 113）最近的公共祖先（ 236）二叉树转链表 （ 114）侧面观察二叉树（ 199）数组转二叉查找树（ 108）二叉查找树的转换（ 538）二叉查找树的节点删除（ 450）插入位置 （ 35）区间查找 （ 34）旋转数组查找（ 33）最长回文串 （ 409）词语模式 （ 290）重复的 DNA 序列（ 187）打家劫舍 （ 198）三角形（ 120）连续的最大字段和（ 53）找零钱 （ 322）课程表（ 207）进击的骑士 （ 1197）岛屿数量 （ 200）