很多时候不懂事

📝 题目描述 题目链接：排序链表 给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。 示例： 示例 1： 12输入：head = [-1,5,3,4,0]输出：[-1,0,3,4,5] 示例 2： 12输入：head = [[1,1],[2,1]]输出：[[1,1],[2,1]] 示例 3： 12输入：head = []输出：[] 提示： 链表中节点的数目在范围 [0, 5 * 10^4] 内 -10^5 <= Node.val <= 10^5 💡 解题思路 方法一：使用multimap map的key是天然有序的，不过考虑到数字有可能重复，我们需要使用multimap。 方法二：自顶向下归并排序✅️ 对链表自顶向下归并排序的过程如下。 找到链表的中点，以中点为分界，将链表拆分成两个子链表。寻找链表的中点可以使用快慢指针的做法，快指针每次移动 2 步，慢指针每次移动 1 步，当快指针到达链表末尾时，慢指针指向的链表节点即为链表的中点； 对两个子链表分别排序（左闭右开区间）； 将两个排序后的子链表合并，得到完整的排序后的链表。可以使...

📝 题目描述 题目链接：随机链表的复制 给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。 构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。 例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。 返回复制链表的头节点。 用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示： val：一个表示 Node.val 的整数。 random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。 你的代码 只 接受原链表的头节点 head 作...

📝 题目描述 题目链接：K 个一组翻转链表 给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。 k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。 你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。 示例： 示例 1： 12输入：head = [1,2,3,4,5], k = 2输出：[2,1,4,3,5] 示例 2： 12输入：head = [1,2,3,4,5], k = 3输出：[3,2,1,4,5] 提示： 链表中的节点数目为 n 1 <= k <= n <= 5000 0 <= Node.val <= 1000 💡 解题思路 方法一：模拟✅️ 首先创建一个哨兵节点，使得第一个子链表的头节点 head 不再特殊化。 我们需要把链表节点按照 k 个一组分组，所以可以使用一个指针 head 依次指向每组的头节点。这个指针每次向前移动 k 步，直至链表结尾。对于每个分组，我们先判断它的长度是否大于等于 k。若是，我们就翻转这部分链表，...

📝 题目描述 题目链接：两两交换链表中的节点 给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。 示例： 示例 1： 12输入：head = [1,2,3,4]输出：[2,1,4,3] 示例 2： 12输入：head = []输出：[] 示例 3： 12输入：head = [1]输出：[1] 提示： 链表中节点的数目在范围 [0, 100] 内 0 <= Node.val <= 100 💡 解题思路 方法一：递归 可以通过递归的方式实现两两交换链表中的节点。 递归的终止条件是链表中没有节点，或者链表中只有一个节点，此时无法进行交换。 如果链表中至少有两个节点，则在两两交换链表中的节点之后，原始链表的头节点变成新的链表的第二个节点，原始链表的第二个节点变成新的链表的头节点。链表中的其余节点的两两交换可以递归地实现。在对链表中的其余节点递归地两两交换之后，更新节点之间的指针关系，即可完成整个链表的两两交换。 用 head 表示原始链表的头节点，新的链表的第二个节点，用 newHea...

📝 题目描述 题目链接：删除链表的倒数第 N 个节点 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。 示例： 示例 1： 12输入：head = [1,2,3,4,5], n = 2输出：[1,2,3,5] 示例 2： 12输入：head = [1], n = 1输出：[] 示例 3： 12输入：head = [1,2], n = 1输出：[1] 提示： 链表中结点的数目为 sz 1 <= sz <= 30 0 <= Node.val <= 100 1 <= n <= sz 💡 解题思路 方法一：计算长度 一种容易想到的方法是，我们首先从头节点开始对链表进行一次遍历，得到链表的长度 LLL。随后我们再从头节点开始对链表进行一次遍历，当遍历到第 L−nL−nL−n 个节点时，它就是我们需要删除的节点。 为了方便实操，我们在头节点前再添加一个哨兵节点，这样得到 LLL 后，我们从哨兵节点开始对链表进行一次遍历，当遍历到第 L−nL−nL−n 个节点时，它就是我们需要删除的节点的前一个节点。 方法二：栈 我们也可以在遍历...

📝 题目描述 题目链接：两数相加 给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。 请你将两个数相加，并以相同形式返回一个表示和的链表。 你可以假设除了数字 0 之外，这两个数都不会以 0 开头。 示例： 示例 1： 123输入：l1 = [2,4,3], l2 = [5,6,4]输出：[7,0,8]解释：342 + 465 = 807. 示例 2： 12输入：l1 = [0], l2 = [0]输出：[0] 示例 3： 12输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]输出：[8,9,9,9,0,0,0,1] 提示： 每个链表中的节点数在范围 [1, 100] 内 0 <= Node.val <= 9 题目数据保证列表表示的数字不含前导零 💡 解题思路 方法一：模拟 由于输入的两个链表都是 逆序 存储数字的位数的，因此两个链表中同一位置的数字可以直接相加。 我们同时遍历两个链表，逐位计算它们的和，并与当前位置的进位值相加。具体而言，如果当前两个链表处相应...

📝 题目描述 题目链接：合并两个有序链表 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例： 示例 1： 12输入：l1 = [1,2,4], l2 = [1,3,4]输出：[1,1,2,3,4,4] 示例 2： 12输入：l1 = [], l2 = []输出：[] 示例 3： 12输入：l1 = [], l2 = [0]输出：[0] 提示： 两个链表的节点数目范围是 [0, 50] -100 <= Node.val <= 100 l1 和 l2 均按 非递减顺序 排列 💡 解题思路 方法一：递归 我们可以如下递归地定义两个链表里的 merge 操作（忽略边界情况，比如空链表等）： {list1[0]+merge(list1[1:],list2)list1[0]<list2[0]list2[0]+merge(list1,list2[1:])​otherwise\begin{cases} list1[0]+merge(list1[1:],list2) & list1[0]<lis...

📝 题目描述 题目链接：环形链表 II 给定一个链表的头节点 head，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。 如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。 不允许修改 链表。 示例： 示例 1： 123输入：head = [3,2,0,-4], pos = 1输出：返回索引为 1 的链表节点解释：链表中有一个环，其尾部连接到第二个节点。 示例 2： 123输入：head = [1,2], pos = 0输出：返回索引为 0 的链表节点解释：链表中有一个环，其尾部连接到第一个节点。 示例 3： 123输入：head = [1], pos = -1输出：返回 null解释：链表中没有环。 提示： 链表中节点的数目范围在范围 [0, 10^4] 内 -10^5 <= Node.val <=...

📝 题目描述 题目链接：环形链表 给你一个链表的头节点 head ，判断链表中是否有环。 如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。 如果链表中存在环 ，则返回 true 。 否则，返回 false 。 示例： 示例 1： 123输入：head = [3,2,0,-4], pos = 1输出：true解释：链表中有一个环，其尾部连接到第二个节点。 示例 2： 123输入：head = [1,2], pos = 0输出：true解释：链表中有一个环，其尾部连接到第一个节点。 示例 3： 123输入：head = [1], pos = -1输出：false解释：链表中没有环。 提示： 链表中节点的数目范围是 [0, 10^4] -10^5 <= Node.val <= 10^5 pos 为 -1 或者链表中的一个有效索引 💡 解题思路 方法一：哈希表...

📝 题目描述 题目链接：回文链表 给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。 回文序列：回文序列是向前和向后读都相同的序列。 示例： 示例 1： 12输入：head = [1,2,2,1]输出：true 示例 2： 12输入：head = [1,2]输出：false 提示： 链表中节点数目在范围[1, 10^5] 内 0 <= Node.val <= 9 💡 解题思路 方法一：复制到数组 这个思路很直观也很简单，就是复制一份数字到数组中去，再利用双指针进行回文判断。 方法二：递归 实际上就是借助栈的性质实现逆序比较。 这种方法需要在递归函数外部预留一个ListNode*的变量，每当返回一层递归，全局变量就要往后移动一个节点，以便进行对比。 方法三：快慢指针 我们可以将链表的后半部分反转（修改链表结构），然后将前半部分和后半部分进行比较。比较完成后我们应该将链表恢复原样。虽然不需要恢复也能通过测试用例，但是使用该函数的人通常不希望链表结构被更改。 该方法虽然可以将空间复杂度降到 ...