找往期文章包括但不限于本期文章中不懂的知识点：
个人主页：我要学编程(ಥ_ಥ)-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 <= 500 <= 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;
}
}
// 判断头节点是否为val
if (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 <= 100l1和l2均按 非递减顺序 排列
思路：创建一个新的带头链表。通过遍历两个链表，比较两者的大小，将 小的val值 对应的节点尾插到这个带头链表中，直至有一方节点结束，再把另一方的节点直接尾插到新链表即可。
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
// 当list1为空或者list1与list2都为空时，直接返回list2
if (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) {
// 尾插cur2
cur.next = cur2;
cur2 = cur2.next;
}else {
// 尾插cur1
cur.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置为null
return afterStart;
}
if (afterStart == null) {
return beforeStart;
}
beforeEnd.next = afterStart;
afterEnd.next = null;
return beforeStart;
}
}这题虽然思路简单，但要注意的细节很多，稍一疏忽，就会犯错。简直就是：虾仁猪心 。
160. 相交链表
给你两个单链表的头节点
headA和headB，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回null。图示两个链表在节点
c1开始相交：
题目数据 保证 整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构 。
自定义评测：
评测系统 的输入如下（你设计的程序 不适用 此输入）：
intersectVal- 相交的起始节点的值。如果不存在相交节点，这一值为0listA- 第一个链表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中节点数目为mlistB中节点数目为n1 <= m, n <= 3 * 1041 <= Node.val <= 1050 <= skipA <= m0 <= 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 <= 105pos为-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 <= 105pos的值为-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;
}
}因为这里在相遇之后，还要执行代码，就必须要判断链表是否为空和只有一个节点无环的情况。
好啦！本期 数据结构之链表的经典笔试题 的学习之旅就到此结束啦！我们下一期再一起学习吧！
![[ue5]建模场景学习笔记（6）——必修内容可交互的地形，交互沙（4）](https://img-blog.csdnimg.cn/direct/ca98f0a2499f4b6486ee44e76090b734.png)
