找往期文章包括但不限于本期文章中不懂的知识点：

个人主页：我要学编程(ಥ_ಥ)-CSDN博客

所属专栏：数据结构（Java版）

目录

203. 移除链表元素

206. 反转链表

876. 链表的中间节点

面试题 02.02. 返回倒数第k个节点

快慢指针的原理分析 

21. 合并两个有序链表

牛客网——链表的回文

牛客网——链表分割

160. 相交链表

 141. 环形链表

142. 环形链表 II

单链表的刷题，点我

下面的这些面试题有一部分在上面这篇博文中，有兴趣可以看一看。

​

下列题目中出现的这个，是出题者想告诉我们这个链表的节点是由什么组成的。 

203. 移除链表元素

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

示例 1：

​

输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]

示例 2：

输入：head = [], val = 1
输出：[]

示例 3：

输入：head = [7,7,7,7], val = 7
输出：[]

提示：

• 列表中的节点数目在范围 [0, 104] 内
• 1 <= Node.val <= 50
• 0 <= val <= 50

思路：就是遍历链表，找到所有值为val的节点，并删除即可。 

class Solution {public ListNode removeElements(ListNode head, int val) {// 删除链表中所有值为节点// 首先判断链表是否为空if (head == null ) {// 链表为空，肯定head为空return head;}ListNode cur = head;while (cur.next != null) {// 找到值为val的前一个节点if (cur.next.val == val) {cur.next = cur.next.next;}else {// 没找到就继续往后找cur = cur.next;}}// 判断头节点是否为valif (head.val == val) {head = head.next;}return head;}
}

206. 反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 1：

​

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

示例 2：

​

输入：head = [1,2]
输出：[2,1]

示例 3：

输入：head = []
输出：[]

提示：

• 链表中节点的数目范围是 [0, 5000]
• -5000 <= Node.val <= 5000

思路：遍历原链表，将其中的所有节点全部头插到原链表中。

class Solution {public ListNode reverseList(ListNode head) {// 当链表为空，或者只有一个节点时，就直接返回原链表if (head == null || head.next == null) {return head;}// 开始头插ListNode cur = head.next;// 这个要变为null，否则就会成环。// 因为这个节点是最后一个节点，而最后一个节点的next值不为null，就会造成错误head.next = null; while (cur != null) {ListNode curNext = cur.next;cur.next = head; head = cur;cur = curNext;}return head;}
}

876. 链表的中间节点

给你单链表的头结点 head ，请你找出并返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点。

示例 1：

​

输入：head = [1,2,3,4,5]
输出：[3,4,5]
解释：链表只有一个中间结点，值为 3 。

示例 2：

​

输入：head = [1,2,3,4,5,6]
输出：[4,5,6]
解释：该链表有两个中间结点，值分别为 3 和 4 ，返回第二个结点。

提示：

• 链表的结点数范围是 [1, 100]
• 1 <= Node.val <= 100

思路一：通过遍历链表得出链表的长度，然后让cur从头节点开始走 长度的一半 的步数，那么这个节点的位置就是中间节点。

思路二：通过快慢指针的方式来解题。快指针fast，一次走两步，慢指针slow，一次走一步。当快指针走到链表的尾节点处时，慢指针就是在当前链表的中间节点。

class Solution {public ListNode middleNode(ListNode head) {ListNode fast = head;ListNode slow = head;// 只要两者有一种情况不满足，就说明走到了尾节点，可以停止遍历了。while (fast != null && fast.next != null) {fast = fast.next.next;slow = slow.next;}return slow;}
}

面试题 02.02. 返回倒数第k个节点

 实现一种算法，找出单向链表中倒数第 k 个节点。返回该节点的值。

注意：本题相对原题稍作改动

示例：

输入： 1->2->3->4->5 和 k = 2
输出： 4

说明：

给定的 k 保证是有效的。

思路一：遍历得出链表的长度，然后用长度减去k，得出的结果就是cur要走的步数。

思路二：通过快慢指针的方式来解题。快指针先走k-1步，然后快指针和慢指针一起走，直至快指针到达尾节点，这时慢指针的位置就是倒数第k个节点的位置。

class Solution {public int kthToLast(ListNode head, int k) {ListNode fast = head;ListNode slow = head;while ((k-1) > 0) {fast = fast.next;k--;}while (fast.next != null) {fast = fast.next;slow = slow.next;}return slow.val;}
}

快慢指针的原理分析 

通过这两题，我们来分析快慢指针的原理。

链表的中间节点 —— 假设有两个人在同一时间赛跑，fast是slow的速度的二倍，当fast到达终点时，这个slow就会在这个总路程的一半处。因此就可以得出中间节点的位置。

返回倒数第k个节点 —— fast先走k-1步，那么fast与slow就相差k-1步，当两者一起走，并且fast走到了终点时，这时fast与slow还是相差k-1步，那么这个slow就是倒数第k个节点（因为fast的位置是倒数第一个节点）。

21. 合并两个有序链表

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 

示例 1：

​

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

示例 2：

输入：l1 = [], l2 = []
输出：[]

示例 3：

输入：l1 = [], l2 = [0]
输出：[0]

提示：

• 两个链表的节点数目范围是 [0, 50]
• -100 <= Node.val <= 100
• l1 和 l2 均按 非递减顺序 排列

思路：创建一个新的带头链表。通过遍历两个链表，比较两者的大小，将 小的val值 对应的节点尾插到这个带头链表中，直至有一方节点结束，再把另一方的节点直接尾插到新链表即可。

class Solution {public ListNode mergeTwoLists(ListNode list1, ListNode list2) {// 当list1为空或者list1与list2都为空时，直接返回list2if (list1 == null) {return list2;}if (list2 == null) {return list1;}// 创建一个新的头节点ListNode head = new ListNode(-1);ListNode cur = head;ListNode cur1 = list1;ListNode cur2 = list2;while (cur1 != null && cur2 != null) {if (cur1.val > cur2.val) {// 尾插cur2cur.next = cur2;cur2 = cur2.next;}else {// 尾插cur1cur.next = cur1;cur1 = cur1.next;}// 因为这一行代码无论走哪里，都会进行，因此放到外边来cur = cur.next;}// 还有一方还剩节点if (cur1 != null) {// 尾插cur1就行了，因为原来就是链表，因此不用循环cur.next = cur1;}if (cur2 != null) {// 尾插cur2就行了，因为原来就是链表，因此不用循环cur.next = cur2;}return head.next;}
}

牛客网——链表的回文

描述

对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。

给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。

测试样例：

1->2->2->1

返回：true

思路：虽然描述很简洁，但是难度却是比较大的一题。按照我们以往写回文的思路，就是定义一个left 和 right 指针指向两头，遍历比较。遇到不相等的就直接返回false，遍历完就返回true。但很可惜这题是单链表不能够反向遍历。既然不能直接反向遍历，那么我们就把这个后面的链表反转一下，变成可以反向遍历的情况。那问题又来了：从哪里开始反转呢？我们想一下，普通回文遍历的结束条件是left < right ，也就是两者相遇或者说是到了中间位置就可以停止了。那么我们这里的反转也就可以从中间位置开始。反转完，之后就可比较了。因此，最终要做的事情就是：

1. 找到链表的中间节点；

2. 从中间位置开始反转；

3. 从两头开始遍历比较。

下面是反转的具体分析过程：

​

public class PalindromeList {public boolean chkPalindrome(ListNode A) {// 当链表为空或者只有一个节点时，必回文if (A == null || A.next == null) {return true;}// 找到中间节点ListNode fast = A;ListNode slow = A;while (fast != null && fast.next != null) {fast = fast.next.next;slow = slow.next;}ListNode cur = slow.next;// 从中间节点往后反转// 当slow走到尾节点时，就可以不必再继续了while (cur != null) {ListNode curNext = cur.next;cur.next = slow;slow = cur;cur = curNext;}// 开始遍历回文// 这里不要用fast，因为fast可能不在尾节点while (A != slow) {if (A.val != slow.val) {return false;}// 当链表长度为偶数时，会出现一种情况（后面细说）if (A.next == slow) {return true;}A = A.next;slow = slow.next; }return true;}
}

​

反转也不能写成下面这样：

    while (slow.next != null) {ListNode cur = slow.next;ListNode curNext = cur.next;cur.next = slow;slow = cur;cur = curNext;}

上面的代码会陷入死循环。因为在最后修改了 slow 的位置，变成了 cur，所以 slow.next 是指向的位置是原来的 slow 。因此最终就陷入了死循环。如下图：

​

最后，我们会发现其实改来改去最终都在兜圈子。 

综上本题来看，难度确实是挺大的，要注意的细节也是挺多的，无愧于 字节跳动 的秋招笔试题。 

牛客网——链表分割

描述

现有一链表的头指针 ListNode* pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。

思路：既然要分割链表，那我们直接按照原来的链表顺序遍历，把小于 x 的节点放到小链表中，其余节点放到大链表中。 

我们就会不假思索的写出下面的代码：

public class Partition {public ListNode partition(ListNode pHead, int x) {// 这题比较虾仁猪心：思路简单，但细节很多// 如果链表为空或者链表只有一个节点，就直接返回该节点if (pHead == null || pHead.next == null) {return pHead;}// 为了更为方便，我们定义头节点和尾节点ListNode beforeStart = null;ListNode beforeEnd = null;ListNode afterStart = null;ListNode afterEnd = null;// 遍历链表，小于放一边，大于放一边，然后小的串大的while (pHead != null) {if (pHead.val < x) {// 尾插到小链表中if (beforeStart == null) {beforeStart = pHead;beforeEnd = pHead;} else {beforeEnd.next = pHead;beforeEnd = beforeEnd.next;}} else {// 尾插到大链表中if (afterStart == null) {afterStart = pHead;afterEnd = pHead;} else {afterEnd.next = pHead;afterEnd = afterEnd.next;}}pHead = pHead.next;}beforeEnd.next = afterStart;return beforeStart;}
}

但上面的代码在测试的时候，会抛出空指针异常。其实就是当小链表为空（链表中所有的值均大于 x）时，这个 beforeStart 为空，那么去访问其 next 值时，就会发生空指针异常。因此，当小链表为空时，直接返回大链表，当大链表为空时，直接返回小链表即可。但很遗憾，又出现了死循环的问题：如下图所示：

因此，我们还得把 afterEnd 的 next 置为null。 通过一系列的纠正，最终的代码如下：

public class Partition {public ListNode partition(ListNode pHead, int x) {// 这题比较虾仁猪心：思路简单，但细节很多// 如果链表为空或者链表只有一个节点，就直接返回该节点if (pHead == null || pHead.next == null) {return pHead;}// 为了更为方便，我们定义头节点和尾节点ListNode beforeStart = null;ListNode beforeEnd = null;ListNode afterStart = null;ListNode afterEnd = null;// 遍历链表，小于放一边，大于放一边，然后小的串大的while (pHead != null) {if (pHead.val < x) {// 尾插到小链表中if (beforeStart == null) {beforeStart = pHead;beforeEnd = pHead;} else {beforeEnd.next = pHead;beforeEnd = beforeEnd.next;}} else {// 尾插到大链表中if (afterStart == null) {afterStart = pHead;afterEnd = pHead;} else {afterEnd.next = pHead;afterEnd = afterEnd.next;}}pHead = pHead.next;}// 把小链表和大链表串起来if (beforeEnd == null) {// 如果小链表为空，那么就直接返回大链表// 那么大链表就是按照原来链表的顺序，即无需将最后节点的next置为nullreturn afterStart;}if (afterStart == null) {return beforeStart;}beforeEnd.next = afterStart;afterEnd.next = null;return beforeStart;}
}

这题虽然思路简单，但要注意的细节很多，稍一疏忽，就会犯错。简直就是：虾仁猪心 。

160. 相交链表

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

图示两个链表在节点 c1 开始相交：

题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

自定义评测：

评测系统 的输入如下（你设计的程序 不适用 此输入）：

• intersectVal - 相交的起始节点的值。如果不存在相交节点，这一值为 0
• listA - 第一个链表
• listB - 第二个链表
• skipA - 在 listA 中（从头节点开始）跳到交叉节点的节点数
• skipB - 在 listB 中（从头节点开始）跳到交叉节点的节点数

评测系统将根据这些输入创建链式数据结构，并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点，那么你的解决方案将被 视作正确答案 。

 

示例 1：

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at '8'
解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,6,1,8,4,5]。
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
— 请注意相交节点的值不为 1，因为在链表 A 和链表 B 之中值为 1 的节点 (A 中第二个节点和 B 中第三个节点) 是不同的节点。换句话说，它们在内存中指向两个不同的位置，而链表 A 和链表 B 中值为 8 的节点 (A 中第三个节点，B 中第四个节点) 在内存中指向相同的位置。

示例 2：

输入：intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Intersected at '2'
解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [1,9,1,2,4]，链表 B 为 [3,2,4]。
在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。

示例 3：

输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：null
解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。
由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
这两个链表不相交，因此返回 null 。

提示：

• listA 中节点数目为 m
• listB 中节点数目为 n
• 1 <= m, n <= 3 * 104
• 1 <= Node.val <= 105
• 0 <= skipA <= m
• 0 <= skipB <= n
• 如果 listA 和 listB 没有交点，intersectVal 为 0
• 如果 listA 和 listB 有交点，intersectVal == listA[skipA] == listB[skipB]

思路： 两个链表相交，有一个特点就是：相交之后的链表长度一定是相同的。假设前面不相交的长度是想等的，定义一个 cur1 指向一个链表，定义一个 cur2 指向另一个链表，去遍历两个链表，当两者不相等时，就一直遍历，直至相等为止。但遗憾的是两者长度会出现不一样的情况，这里依然是使用快慢指针的方法。当长度不相等时，就让 长度长的链表 先走 两者的差值步数，然后再一起走，那么最终的结果一定是两者一起走到相等或者两者走到都为 null。最终的步骤：

1、先算出两者的长度，求其长度差。

2、再让长度长的链表走长度差步

3、接着两者一起走，判断是否相等

public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {// 先算出各自长度，让长的链表走两者长度的差值步，再一起走，如果相遇则其相交。ListNode cur1 = headA;ListNode cur2 = headB;int len1 = 0;int len2 = 0;while (cur1 != null) {len1++;cur1 = cur1.next;}while (cur2 != null) {len2++;cur2 = cur2.next;}if (len1 > len2) {// 让headA走差值步cur1 = headA;cur2 = headB;int len = len1 - len2;while (len-- > 0) {cur1 = cur1.next;}// 开始比较while (cur1 != cur2) {cur1 = cur1.next;cur2 = cur2.next;}// 走到这里，有两种情况：1、cur1与cur2 都为空了，跳出了循环// 2、两者确实是相遇了。 我们只需判断一下即可if (cur1 == null) {return null;}// 其实这里不判断，也可以运行通过，因为题目要求不相遇就返回null，// 而比较到null时，cur1也是null，所以返回cur1也是对的（碰巧）。return cur1;}else {// 让headB走差值步cur1 = headA;cur2 = headB;int len = len2 - len1;while (len-- > 0) {cur2 = cur2.next;}// 开始比较while (cur1 != cur2) {cur1 = cur1.next;cur2 = cur2.next;}// 走到这里，有两种情况：1、cur1与cur2 都为空了，跳出了循环// 2、两者确实是相遇了。 我们只需判断一下即可if (cur1 == null) {return null;}// 其实这里不判断，也可以运行通过，因为题目要求不相遇就返回null，// 而比较到null时，cur1也是null，所以返回cur1也是对的（碰巧）。return cur1;}}
}

上面的代码在后面一起走的部分中大部分代码是一致的，因此就可以简化为下面这样：

public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {// 先算出各自长度，让长的链表走两者长度的差值步，再一起走，如果相遇则其相交。ListNode cur1 = headA;ListNode cur2 = headB;int len1 = 0;int len2 = 0;while (cur1 != null) {len1++;cur1 = cur1.next;}while (cur2 != null) {len2++;cur2 = cur2.next;}// 假设headA为长链表int len = len1-len2;cur1 = headA;cur2 = headB;if (len < 0) {// 说明headB是长链表len = - len;cur1 = headB;cur2 = headA;}// 走到这里，长链表一定已经确定了while (len-- > 0) {cur1 = cur1.next;}while (cur1 != cur2) {cur1 = cur1.next;cur2 = cur2.next;}if (cur1 == null) {return null;}return cur1;}
}

 141. 环形链表

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ，则返回 true 。 否则，返回 false 。

示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

输入：head = [1], pos = -1
输出：false
解释：链表中没有环。

提示：

• 链表中节点的数目范围是 [0, 104]
• -105 <= Node.val <= 105
• pos 为 -1 或者链表中的一个 有效索引 。

思路：快慢指针。当一个链表没有环，那么肯定是快指针先走到终点，如果一个链表有环，则快指针会先入环，接着慢指针再入环，最终快慢指针会相遇（一定是快指针走两步，慢指针走一步，这样快指针才不会包含慢指针）。如果快指针走三步，就有可能出现慢指针一直在快指针中间的情况。

public class Solution {public boolean hasCycle(ListNode head) {// 如果链表为空或者链表的第一个节点的next为空，则说明没有成环if (head == null || head.next == null) {return false;}ListNode fast = head;ListNode slow = head;// 快指针如果遇到结尾的情况就可以停止了while (fast != null && fast.next != null) {fast = fast.next.next;slow = slow.next;// 一定要走完才能判断if (fast == slow) {return true;}}return false;}
}

其实，我们仔细观察会发现：在快指针还没开始走的时候，while循环的判断条件和前面的if判断条件是一样的，都是判断链表是否为空或者是链表的第一个节点的 next 值是是否为空。

public class Solution {public boolean hasCycle(ListNode head) {ListNode fast = head;ListNode slow = head;// 快指针如果遇到结尾的情况就可以停止了while (fast != null && fast.next != null) {fast = fast.next.next;slow = slow.next;// 一定要走完才能判断if (fast == slow) {return true;}}return false;}
}

142. 环形链表 II

给定一个链表的头节点  head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改 链表。

示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。

提示：

• 链表中节点的数目范围在范围 [0, 104] 内
• -105 <= Node.val <= 105
• pos 的值为 -1 或者链表中的一个有效索引

思路： 这个题目的意思就是让我们找到链表的第一个成环的节点。如下图所示：

上面那种情况只是我们认为的理想情况：慢指针入环时，快指针刚好只走完一圈，但是实际走完几圈我们是不确定的，因此可以设 n 为快指针走的圈数，带入求解的结果就是：x = n*m - y = (n-1)*m + (m-y)，最终结果还是我们前面的结论。因为 (n-1)只是圈数，最终还是会停在这个相遇点。

这里最重要的是抓住：快指针走的路程是慢指针的两倍。 

1、找到相遇点

2、慢指针从头走，快指针从相遇点走，都以相同的速度。

public class Solution {public ListNode detectCycle(ListNode head) {// 找到相遇点ListNode fast = head;ListNode slow = head;while (fast != null && fast.next != null) {fast = fast.next.next;slow = slow.next;// 相遇就停下来if (slow == fast) {break;}}// 链表里没有环的情况有几种：if (fast != slow || head == null || head.next == null) {// 说明没有环return null;}// slow从链表头开始走，fast从相遇点开始走slow = head;while (slow != fast) {fast = fast.next;slow =slow.next;}return slow;}
}

因为这里在相遇之后，还要执行代码，就必须要判断链表是否为空和只有一个节点无环的情况。 

好啦！本期 数据结构之链表的经典笔试题 的学习之旅就到此结束啦！我们下一期再一起学习吧！