难度: Hard
给你链表的头节点 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]提示：
n1 <= k <= n <= 50000 <= Node.val <= 1000进阶：你可以设计一个只用 O(1) 额外内存空间的算法解决此问题吗？
运行时间: 52 ms
内存: 16 MB
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
if head is None:
return None
a = b = head
for _ in range(k):
if b is None:
return head
b = b.next
def reverse(h, t):
pre = None
cur = h
while cur != t:
tmp = cur.next
cur.next = pre
pre = cur
cur = tmp
return pre
new_head = reverse(a, b)
a.next = self.reverseKGroup(b, k)
return new_head
这个题解使用了递归的思路。首先判断链表长度是否小于k，如果是则直接返回原链表。否则，找到第k个节点，作为当前要反转的子链表的尾节点。然后调用reverse函数反转从head到第k个节点这一段的子链表。反转完后，head成为子链表的尾节点，递归处理之后的节点，将其作为head的next。最后返回反转后的链表的头节点，即反转前的第k个节点。
时间复杂度: O(n)
空间复杂度: O(n)
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
# 如果链表为空，直接返回
if head is None:
return None
# a为子链表的头，b为子链表的尾的下一个节点
a = b = head
# 寻找子链表的尾节点，使其与后面的链表断开
for _ in range(k):
if b is None:
return head
b = b.next
# 定义反转链表的函数
def reverse(h, t):
pre = None
cur = h
while cur != t:
tmp = cur.next
cur.next = pre
pre = cur
cur = tmp
return pre
# 反转前k个节点，得到子链表的新头节点
new_head = reverse(a, b)
# 原来的头节点现在是子链表的尾节点，其next连接递归处理之后的节点
a.next = self.reverseKGroup(b, k)
return new_head
在题解的代码中，这一点通过在寻找子链表的尾节点时的循环中实现。循环试图移动b指针k次，如果在达到k次之前b变成了None，说明剩余节点数小于k，这时函数会直接返回head，即不对这部分进行翻转，保持其原有顺序。这是通过`if b is None: return head`这行代码实现的。
对于最大节点数5000，如果每组k非常小，递归深度可以接近5000/k，这可能导致栈溢出，特别是在栈空间有限的环境下。虽然现代编译器和操作系统对递归的优化较好，但在极端情况下替换为迭代方法以避免栈溢出是一个更安全的选择。迭代方法通常使用循环来替代递归逻辑，能够有效减少对栈空间的使用。
在这种参数选择中，头节点h是反转部分的起始节点，而尾节点的下一个节点t是反转部分的结束位置（不包括t）。这使得函数在到达t之前就停止反转，因此可以方便地处理部分链表的反转而不影响其他部分。此外，这种参数设置也便于在主函数中连接已经反转的部分与未反转的部分，因为在反转结束后，我们知道t节点是未反转部分的开始，而函数返回的是反转部分的新头节点。
在并发环境下，链表的指针修改操作不是线程安全的。如果有多个线程可能同时修改链表的同一部分，这可能会导致数据竞争和不一致的状态。在这种情况下，确实需要通过加锁机制来保证链表操作的原子性和一致性。可以使用互斥锁（mutex）来保护整个链表或链表的关键部分，在进行修改之前获取锁，在修改完成后释放锁，从而保证操作的线程安全性。