删除链表的倒数第 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]
双指针
思路
- 虚拟头节点：使用
dummy节点简化边界处理，例如删除头节点时，无需特殊处理逻辑。 - 快慢指针移动：
fast指针先移动 n+1 步（多移动一步以便slow停留在目标节点的前一个节点）。之后同时移动fast和slow，直到fast到达链表末尾。 - 删除目标节点：
slow.next指向slow.next.next，跳过目标节点。 - 返回结果：返回
dummy.next，即删除目标节点后的链表头节点。
代码
class Solution:
def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
dummy = ListNode(0, head) # 虚拟头节点
fast = dummy
slow = dummy
# 让 fast 指针先移动 n+1 步
for _ in range(n + 1):
fast = fast.next
# 同时移动 fast 和 slow，直到 fast 到达链表末尾
while fast:
fast = fast.next
slow = slow.next
# 删除 slow.next（即倒数第 n 个节点）
slow.next = slow.next.next
# 返回链表的头节点
return dummy.next
复杂度
- 时间复杂度：O(n): 遍历链表两次：一次移动
fast，一次移动fast和slow。 - 空间复杂度：O(1): 使用常量空间。
注意事项
- 特殊情况处理：
- 如果需要删除的是头节点，应直接更新
head。
- 如果需要删除的是头节点，应直接更新
- 确保
slow指针操作正确：- 使用一个虚拟头节点 (
dummy) 简化删除逻辑，避免处理边界条件（例如删除头节点）时的复杂性。
- 使用一个虚拟头节点 (
- 返回结果：
- 返回虚拟头节点的
next作为链表的头节点，确保返回值始终正确。
- 返回虚拟头节点的
两次遍历
思路
第一次遍历统计链表长度第二次遍历时删除倒数第n个节点
两两交换链表中的节点
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
示例 1：
输入：head = [1,2,3,4] 输出：[2,1,4,3]
示例 2：
输入：head = [] 输出：[]
示例 3：
输入：head = [1] 输出：[1]
方法
思路
- 虚拟头节点：使用
dummy节点的next指向原链表的头节点，简化头节点的交换逻辑。 - 循环条件：检查
pre_node.next和pre_node.next.next是否存在，确保当前的两个节点可以被交换。 - 节点交换：交换两个节点
node1和node2的指针：pre_node.next指向node2。node1.next指向node2.next。node2.next指向node1。
- 更新指针：更新
pre_node为node1，继续下一对节点的交换。 - 返回结果：最后返回
dummy.next，即交换后的链表头节点。
代码
class Solution:
def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
# 使用虚拟头节点
dummy = ListNode(0, head)
pre_node = dummy
# 遍历链表，按两两节点交换
while pre_node.next and pre_node.next.next:
node1 = pre_node.next
node2 = node1.next
# 交换节点
pre_node.next = node2
node1.next = node2.next
node2.next = node1
# 更新前驱节点
pre_node = node1
# 返回交换后的链表头节点
return dummy.next
复杂度分析
- 时间复杂度：O(n)
- 遍历链表一次，每次交换两个节点。
- 空间复杂度：O(1)
- 使用常量级别的额外空间，无递归或额外数据结构。
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]
方法
思路
- 初始化：
- 创建一个虚拟头节点
dummy，将其next指向链表头部，方便统一处理头节点翻转的情况。 - 使用一个指针
pre_node，初始指向dummy，作为每组翻转后链表的连接点。
- 创建一个虚拟头节点
- 分组检查：
- 使用
check_k函数，检查从当前节点开始是否有足够的 kkk 个节点。如果不足 kkk，结束翻转操作。
- 使用
- 分组翻转：
- 对当前组的 k个节点调用
reverse_listnode函数进行翻转：- 翻转函数返回翻转后的新头节点和新尾节点。
- 翻转完成后，更新当前组的前后链接：
- 翻转后的新头节点通过
pre_node.next连接到前一部分链表。 - 翻转后的新尾节点通过
new_tail.next连接到未翻转部分链表。
- 翻转后的新头节点通过
- 对当前组的 k个节点调用
- 移动指针：
- 将
pre_node更新为当前组的尾节点，继续处理下一组。
- 将
- 返回结果：
- 最后返回
dummy.next作为新链表的头节点。
- 最后返回
代码
class Solution:
def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
if not head or k == 1:
return head
# 翻转链表的前 k 个节点，返回翻转后的头和尾
def reverse_listnode(head, k):
prev = None
curr = head
for _ in range(k):
next_node = curr.next
curr.next = prev
prev = curr
curr = next_node
return prev, head # 返回翻转后的头和尾
# 检查是否有足够的 k 个节点
def check_k(node, k):
count = 0
while node and count < k:
node = node.next
count += 1
return count == k
# 使用虚拟头节点
dummy = ListNode(0, head)
pre_node = dummy
# 按 k 分组翻转链表
while check_k(pre_node.next, k):
group_head = pre_node.next # 当前组的头节点
group_tail = pre_node # 当前组的尾节点将更新
for _ in range(k):
group_tail = group_tail.next
next_group = group_tail.next # 下一组的起点
# 翻转当前组
new_head, new_tail = reverse_listnode(group_head, k)
# 更新前后链接
pre_node.next = new_head
new_tail.next = next_group
# 更新 pre_node 为当前组的尾节点
pre_node = new_tail
return dummy.next
复杂度
- 时间复杂度：O(n)
- 遍历链表一次，每次翻转 k 个节点，整体复杂度为线性。
- 空间复杂度：O(1)
- 除了少量变量外，没有额外的空间使用。
优化
优化思路
- 减少多余的长度检查：
- 在传统实现中，会多次检查是否有足够的 k 个节点（如
check_k函数）。可以通过一次遍历统计链表长度来避免重复检查，从而优化性能。
- 在传统实现中，会多次检查是否有足够的 k 个节点（如
- 减少递归使用（如果有）：
- 部分实现可能使用递归处理每组节点的翻转。虽然代码更简洁，但递归会导致额外的栈空间消耗，可能引发栈溢出。在实现中尽量使用迭代。
- 一次性计算尾部节点更新：
- 翻转组内的节点时，可以避免重复更新指针，将尾部节点的更新集中处理。
- 整合逻辑，减少冗余变量：
- 通过合并前后链接的处理逻辑和翻转逻辑，可以减少变量的使用和逻辑的复杂度。
代码
class Solution:
def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
# 如果链表为空或 k 为 1（无需翻转），直接返回原链表
if not head or k == 1:
return head
# 计算链表长度
length = 0
cur = head
while cur: # 遍历链表统计节点数
length += 1
cur = cur.next
# 定义虚拟头节点 dum，便于处理头节点翻转的特殊情况
# p0 指向每次翻转前的前驱节点，初始为虚拟头节点
p0 = dum = ListNode(0, head)
pre_node = None # 翻转过程中的前驱节点
cur_node = head # 当前处理的节点（翻转组的起点）
# 当剩余节点数 >= k 时，继续分组翻转
while length >= k:
# 翻转当前组的 k 个节点
for i in range(k):
next_node = cur_node.next # 保存下一个节点，避免链表断裂
cur_node.next = pre_node # 翻转当前节点的指向
pre_node = cur_node # 更新前驱节点为当前节点
cur_node = next_node # 更新当前节点为下一个节点
# 连接翻转后的链表部分
next_node = p0.next # 当前组翻转前的头节点（翻转后是尾节点）
next_node.next = cur_node # 当前组的尾节点连接到未翻转部分的头节点
p0.next = pre_node # 上一组的尾节点连接到当前组的头节点
# 更新指针，为下一组翻转做准备
p0 = next_node # p0 更新为当前组的尾节点
pre_node = None # 重置前驱节点
length -= k # 减少剩余节点数
# 返回虚拟头节点的 next，即翻转后的链表头节点
return dum.next
思路分析
首先是要遍历找到链表长度，之后根据长度每k长翻转一次链表，重点是翻转后的前后连接该如何修改。为了修改前后连接，可以使用一个变量 p0 作为本轮目标翻转链表的前一个Node，而因为当我们翻转完当前链表时我们的三个变量pre_node, cur_node 和next_node分别为当前链表翻转后的head节点，下一次要翻转的head节点。因此我们可以先使用p0.next作为翻转后的尾节点。此时当前翻转后的首尾节点，当前链表前节点与链表后节点就都知道了，现在就可以进行修改连接。
在使用p0.next作为翻转后的尾节点后我们可以将前节点p0与翻转后首节点pre_node连接，之后将翻转后尾节点与链表后节点cur_node 连接，这样就修改了当前链表的前后连接，最后可以将p0重新设置为下一个翻转链表的前节点，也就是现在的next_node
复杂度
- 时间复杂度：O(n)
- 统计链表长度：O(n)。
- 按组翻转：每个节点被访问一次，总复杂度为 O(n)。
- 空间复杂度：O(1)
- 只使用了常量级别的辅助变量，没有额外的数据结构。