29、删除链表的倒数第N个结点
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
示例 1：
输入：head = [1,2,3,4,5], n = 2 输出：[1,2,3,5]
示例 2：
输入：head = [1], n = 1 输出：[]
示例 3：
输入：head = [1,2], n = 1 输出：[1]
思路解答：
- 使用两个指针 fast 和 slow，初始时都指向头节点。
- 让 fast 先向前移动 n+1 步，这样 fast 和 slow 之间相隔 n 个节点。
- 接着同时移动 fast 和 slow，直到 fast 到达链表末尾，此时 slow 就指向要删除节点的前一个节点。
- 修改指针，将 slow.next 指向 slow.next.next，即删除倒数第 n 个节点。
def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
dummy = ListNode(0)
dummy.next = head
fast = dummy
slow = dummy
# 让 fast 先向前移动 n+1 步
for _ in range(n + 1):
fast = fast.next
# 同时移动 fast 和 slow
while fast is not None:
fast = fast.next
slow = slow.next
# 删除倒数第 n 个节点
slow.next = slow.next.next
return dummy.next
30、两两交换链表中的节点
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
示例 1：
输入：head = [1,2,3,4] 输出：[2,1,4,3]
示例 2：
输入：head = [] 输出：[]
示例 3：
输入：head = [1] 输出：[1]
提示：
- 链表中节点的数目在范围 [0, 100] 内
- 0 <= Node.val <= 100
思路解答：
1、递归的终止条件是当前节点或者下一个节点为空。
2、交换当前节点和下一个节点，然后递归地交换剩余的节点。
3、返回交换后的头节点。
def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]: if not head or not head.next: return head # 交换当前节点和下一个节点 next_node = head.next head.next = swapPairs(next_node.next) next_node.next = head return next_node31、K个一组翻转链表
给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。
k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。
示例 1：
输入：head = [1,2,3,4,5], k = 2 输出：[2,1,4,3,5]
示例 2：
输入：head = [1,2,3,4,5], k = 3 输出：[3,2,1,4,5]
提示：
- 链表中的节点数目为 n
- 1 <= k <= n <= 5000
- 0 <= Node.val <= 1000
思路解答：
- 递归函数：
- 定义了一个递归函数 reverseLinkedList(head, k)，用于翻转以 head 开头的链表的前 k 个节点。
- 在函数内部，首先向前移动 k 步，找到需要翻转的节点范围。
- 如果找到了 k 个节点，递归调用函数翻转剩余部分，并将当前部分翻转后的头节点返回。
- 翻转操作：
- 在翻转操作中，使用迭代的方式将当前 k 个节点进行翻转，然后将翻转后的部分连接起来。
- 递归调用：
- 在主函数中，直接调用递归函数 reverseLinkedList(head, k)，开始处理整个链表。
- 返回结果：
- 最终返回处理完整个链表后的头节点。
def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]: def reverseLinkedList(head, k): count = 0 curr = head while curr and count < k: curr = curr.next count += 1 if count == k: reversed_head = reverseLinkedList(curr, k) while count > 0: next_node = head.next head.next = reversed_head reversed_head = head head = next_node count -= 1 head = reversed_head return head return reverseLinkedList(head, k)32、随机链表的复制
给你一个长度为 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 作为传入参数。
示例 1：
输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]] 输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]
示例 2：
输入：head = [[1,1],[2,1]] 输出：[[1,1],[2,1]]
示例 3：
输入：head = [[3,null],[3,0],[3,null]] 输出：[[3,null],[3,0],[3,null]]
提示：
- 0 <= n <= 1000
- -104 <= Node.val <= 104
- Node.random 为 null 或指向链表中的节点。
思路解答：
- 第一次遍历：创建一个哈希表 node_map，并在遍历的过程中，将原节点和对应的新节点存储在哈希表中。
- 第二次遍历：根据原节点的指针关系，更新新节点的指针关系，包括 next 指针和 random 指针。
- 最后返回哈希表中存储的头节点对应的新节点，即深拷贝后的链表头。
def copyRandomList(self, head: Optional[Node]) -> Optional[Node]: if not head: return None # 创建哈希表用于存储原节点和新节点的对应关系 result_map = {} # 第一次遍历，复制节点并存储到哈希表 curr = head while curr: result_map[curr] = Node(curr.val) curr = curr.next # 第二次遍历，处理新节点的指针关系 curr = head while curr: if curr.next: result_map[curr].next = result_map[curr.next] if curr.random: result_map[curr].random = result_map[curr.random] curr = curr.next return result_map[head]
- 递归函数：