链表经典面试题上

目录

创作不易，如若对您有帮助，还望三连，谢谢！！！

题目一：203. 移除链表元素 - 力扣（LeetCode）

题目二：206. 反转链表 - 力扣（LeetCode）

题目三：876. 链表的中间结点 - 力扣（LeetCode）

题目四：面试题 02.02. 返回倒数第 k 个节点 - 力扣（LeetCode）

题目五：21. 合并两个有序链表 - 力扣（LeetCode）

题目六：面试题 02.04. 分割链表 - 力扣（LeetCode）

题目七：160. 相交链表 - 力扣（LeetCode）

题目八：141. 环形链表 - 力扣（LeetCode）

拓展问题：

---

创作不易，如若对您有帮助，还望三连，谢谢！！！

之前我们学习了单链表，实现了单链表的一系列的功能，今天我们来讲解一下链表的一些经典面试题目，以便巩固我们对链表的理解。

话不多说，我们直接来看题目：

题目一：203. 移除链表元素 - 力扣（LeetCode）

我们看题目：给定一个单链表和头结点，让我们删除所有满足 Node.val == val 的节点，并返回 新的头节点 。

思路：创建新链表，遍历原链表，将原链表中值不为val的节点尾插到新链表中。我们之前在实现单链表功能中写过尾插的方法，所以这里就不在赘述，代码如下：

这段代码创建了一个新的带头单链表，并将原链表中满足条件的节点进行尾插，最后释放了dummy，防止内存泄漏。

那么，这段代码有问题吗？有什么问题呢？

有小伙伴会说：没有考虑链表为空的情况，题目说了链表可能为空。仔细看我们这段代码：当head为空时，不会进入while循环，最后返回NULL,没有什么问题，那么我们代码是正确的吗？我们先运行一下代码：

结果有问题，为什么最后一个值为6的节点没有被删除呢？我们回头看一下我们尾插的代码：

最后一步，pcur指向最后一个节点，节点的值为6，不满足条件，故pcur指向NULL,跳出while循环，但此时新链表最后一个节点（值为5）的next指针指向哪里呢？我们并没有修改它，所以它会指向原链表的最后一个节点，所以才会引发错误，所以我们只需要在while循环后加入一个 ：newTail->next=NULL即可，修改后的代码如下：

题目二：206. 反转链表 - 力扣（LeetCode）

这一题同样提供两种思路：

思路一：创建新链表，遍历原链表，在新链表中进行头插操作，从而达到反转链表的目的。

思路二：定义三个指针，用三个指针遍历链表，在原链表上完成反转操作。

思路一我们之前也讲过头插，代码比较简单，我们主要讲一下思路二：

代码如下：

题目三：876. 链表的中间结点 - 力扣（LeetCode）

这里的思路是快慢指针：创建两个指针，慢指针一次走一步，快指针一次走两步，最后快指针走到尾时，慢指针指向的节点就是中间节点。

思路示意图如下：

那么我们肯定要写一个循环，循环结束条件是什么呢？看上面的示意图，我们可以得出是：

fast不为空，并且fast->next不为空，代码如下：

注意：循环判断条件不能交换位置，即写成：fast->next &&fast,因为当链表节点个数为奇数时，最后fast为NULL,改变顺序不就变成对空指针解引用了吗？

题目四：面试题 02.02. 返回倒数第 k 个节点 - 力扣（LeetCode）

 

思路：快慢指针，两个指针初始相差k步，最后fast指向NULL时，slow指向的就是链表倒数第k个节点。思路示意图如下：

代码如下：

题目五：21. 合并两个有序链表 - 力扣（LeetCode）

思路：创建一个新链表，遍历原来两个链表，将两个链表节点的值进行比较，值晓得节点尾插到新链表后

代码如下：

这段代码要注意的一点是：出了while循环后有两种情况：要么是list1为空，要么是list2为空，所以我们要连接不为空的链表。

题目六：面试题 02.04. 分割链表 - 力扣（LeetCode）

思路：创建两个带头链表，一个小链表，一个大链表

把原链表中值小于x的节点尾插到小链表中，把原链表中值大于x的节点尾插到大链表中

最后，把小链表的尾连接到大链表的第一个有效节点上。

代码如下：

仔细看看上面代码，看看有没有问题？

看似没有什么问题，我们来运行一下：

这是为什么呢？我们来分析一下：

最后我们的代码运行结果为上图所示，这时有一个问题：大链表最后一个节点的next指针指向谁呢？我们并没有改变它的next指针，所以他指向的是小链表中的最后一个节点，示意图如下：

这不变成带环链表了吗？所以才会超出时间限制，我们只需要把大链表的最后一个节点指向NULL，即可，代码如下：

题目七：160. 相交链表 - 力扣（LeetCode）

思路：先遍历两个链表，记录两个链表的节点个数m，n

然后通过尾节点是否相等来判断两个链表是否相交，因为两个链表只要相交，尾节点必定为同一个。

最后快慢指针，快指针比慢指针多走m--n的绝对值步，从而找到第一个交点。思路图如下：

代码如下：

题目八：141. 环形链表 - 力扣（LeetCode）

首先，我们先说思路：快慢指针，快指针一次走两步，慢指针一次走一步

如链表有环，必能在环中相遇。

代码如下：

那么，为什么有环的话，快慢指针一定会在环中相遇呢？讲解在下图：

这不就变成追击相遇问题了吗？fast速度相当于2，slow速度相当于1，两者距离为△x，变换参考系，以slow为参考系，fast相对速度为1，所以一定能追上。

拓展问题：

如果fast一次走3步，4步....n步，还一定能在环中相遇吗？

我们在下篇文章中接着讲解这个问题。