链表
#algorithm/linkedList
206. 反转链表
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
示例 1：
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]
示例 2：
输入：head = [1,2] |
示例 3：
输入：head = [] |
提示：
- 链表中节点的数目范围是
[0, 5000] -5000 <= Node.val <= 5000
三指针
/** |
递归
/** |
/** |
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 |
示例 2：
输入：intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1 |
示例 3：
输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2 |
提示：
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]
思路：
根据题目意思
如果两个链表相交，那么相交点之后的长度是相同的
我们需要做的事情是，让两个链表从同距离末尾同等距离的位置开始遍历。这个位置只能是较短链表的头结点位置。
为此，我们必须消除两个链表的长度差
- 指针 pA 指向 A 链表，指针 pB 指向 B 链表，依次往后遍历
- 如果 pA 到了末尾，则 pA = headB 继续遍历
- 如果 pB 到了末尾，则 pB = headA 继续遍历
比较长的链表指针指向较短链表head时，长度差就消除了
如此，只需要将最短链表遍历两次即可找到位置
source code
public class Solution { |
141. 环形链表
给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ，则返回 true 。 否则，返回 false 。
示例 1：
输入：head = [3,2,0,-4], pos = 1 |
示例 2：
输入：head = [1,2], pos = 0 |
示例 3：
输入：head = [1], pos = -1 |
提示：
- 链表中节点的数目范围是
[0, 104] -105 <= Node.val <= 105pos为-1或者链表中的一个 有效索引 。
思路：
快慢指针 fast 走两步 slow 走一步，如果是环最后肯定会相遇
source code
class Solution(object): |
142. 环形链表 II
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改 链表。
示例 1：
输入：head = [3,2,0,-4], pos = 1 |
示例 2：
输入：head = [1,2], pos = 0 |
示例 3：
输入：head = [1], pos = -1 |
提示：
- 链表中节点的数目范围在范围
[0, 104]内 -105 <= Node.val <= 105pos的值为-1或者链表中的一个有效索引
92. 反转链表 II
给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。
示例 1：
输入：head = [1,2,3,4,5], left = 2, right = 4 |
示例 2：
输入：head = [5], left = 1, right = 1 |
提示：
- 链表中节点数目为
n 1 <= n <= 500-500 <= Node.val <= 5001 <= left <= right <= n
思路：
source code
class Solution: |
143. 重排链表
给定一个单链表 L 的头节点 head ，单链表 L 表示为：
$L0 → L1 → … → Ln - 1 → Ln$
请将其重新排列后变为：
$L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …$
不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
示例 1：
输入：head = [1,2,3,4] |
示例 2：
输入：head = [1,2,3,4,5] |
提示：
- 链表的长度范围为
[1, 5 * 104] 1 <= node.val <= 1000
思路：
找到链表的midNode, 然后反转mid作为head2
依次连接head1和head2
source code
class Solution: |
25. K 个一组翻转链表
给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。
k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。
示例 1：
输入：head = [1,2,3,4,5], k = 2 |
示例 2：
输入：head = [1,2,3,4,5], k = 3 |
提示：
- 链表中的节点数目为
n 1 <= k <= n <= 50000 <= Node.val <= 1000
思路：
步骤分解:
链表分区为已翻转部分+待翻转部分+未翻转部分
每次翻转前，要确定翻转链表的范围，这个必须通过 k 此循环来确定
需记录翻转链表前驱和后继，方便翻转完成后把已翻转部分和未翻转部分连接起来
初始需要两个变量
pre和end，pre代表待翻转链表的前驱，end代表待翻转链表的末尾经过k此循环，
end到达末尾，记录待翻转链表的后继next = end.next翻转链表，然后将三部分链表连接起来，然后重置
pre和end指针，然后进入下一次循环特殊情况，当翻转部分长度不足
k时，在定位end完成后，end==null，已经到达末尾，说明题目已完成，直接返回即可时间复杂度为 $O(n * K)$ 最好的情况为 $O(n)$ 最差的情况未 $O(n^2)$
空间复杂度为 $O(1)$ 除了几个必须的节点指针外，我们并没有占用其他空间
![]()
class Solution:
def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
dummy = ListNode(0)
dummy.next = head
pre = dummy
end = dummy
while end.next:
for i in range(k):
end = end.next
if not end: break
if not end: break
start = pre.next
next = end.next
end.next = None
pre.next = self.reverse(start)
start.next = next
end = start
pre = end
return dummy.next
def reverse(self, head):
prev, cur = None, head
while cur:
next = cur.next
cur.next = prev
prev = cur
cur = next
return prev```
# [19. 删除链表的倒数第 N 个结点](https://leetcode.cn/problems/remove-nth-node-from-end-of-list/)
给你一个链表，删除链表的倒数第 `n` 个结点，并且返回链表的头结点。
**示例 1：**
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]
|
输入：head = [1], n = 1
输出：[]
|
输入：head = [1,2], n = 1
输出：[1]
|
思路：
弹出栈的第 n 个节点就是需要删除的节点，并且目前栈顶的节点就是待删除节点的前驱节点。
source code
class Solution: |
82. 删除排序链表中的重复元素 II
给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。
示例 1：
输入：head = [1,2,3,3,4,4,5] |
示例 2：
输入：head = [1,1,1,2,3] |
提示：
- 链表中节点数目在范围
[0, 300]内 -100 <= Node.val <= 100- 题目数据保证链表已经按升序 排列
思路：
把重复节点删除即可
source code
class Solution: |
1261. 在受污染的二叉树中查找元素
给出一个满足下述规则的二叉树：
root.val == 0- 如果
treeNode.val == x且treeNode.left != null，那么treeNode.left.val == 2 * x + 1 - 如果
treeNode.val == x且treeNode.right != null，那么treeNode.right.val == 2 * x + 2
现在这个二叉树受到「污染」，所有的 treeNode.val 都变成了 -1。
请你先还原二叉树，然后实现 FindElements 类：
FindElements(TreeNode* root)用受污染的二叉树初始化对象，你需要先把它还原。bool find(int target)判断目标值target是否存在于还原后的二叉树中并返回结果。
示例 1：
输入： |
示例 2：
输入： |
示例 3：
输入： |
提示：
TreeNode.val == -1- 二叉树的高度不超过
20 - 节点的总数在
[1, 10^4]之间 - 调用
find()的总次数在[1, 10^4]之间 0 <= target <= 10^6
思路：
方法一：哈希表
从 $\textit{root}$ 出发 DFS 这棵树，除了传入当前节点 $\textit{node}$，还传入需要还原的值 $\textit{val}$。
递归左儿子：传入 $\textit{val}\cdot 2 + 1$。
递归右儿子：传入 $\textit{val}\cdot 2 + 2$。
递归的同时，把还原后的节点值加到一个哈希表中。这样对于 $\texttt{find}$，只需要看 $\textit{target}$是否在哈希表中即可。
source code
class FindElements: |
148. 排序链表
给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
示例 1：
输入：head = [4,2,1,3] |
示例 2：
ww
输入：head = [-1,5,3,4,0] |
示例 3：
输入：head = [] |
提示：
- 链表中节点的数目在范围
[0, 5 * 104]内 -105 <= Node.val <= 105
思路:
归并排序（递归法）
source code
class Solution: |