🙃O(1)空间下随便反转链表
206. 反转链表 - 力扣（Leetcode）
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
示例 1：
输入： head = [1,2,3,4,5]
输出： [5,4,3,2,1]
示例 2：
输入： head = [1,2]
输出： [2,1]
示例 3：
输入： head = []
输出： []
代码如下：
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
dummy = ListNode()
while head:
nex = head.next
head.next = dummy.next
dummy.next = head
head = nex
return dummy.next
这是一个迭代法翻转链表的实现，可以看作是对链表进行头插法的操作。它的具体实现思路如下：
-
初始化一个空链表
dummy，作为反转后的链表的头节点。 -
遍历原链表，每次取出当前节点
head，并将其后继节点nex保存下来。 -
将
head插入到dummy的后面，即head.next = dummy.next，dummy.next = head。这样就把head放到了dummy的前面，相当于反转了链表的一部分。 -
将当前节点移动到下一个节点，即
head = nex。 -
重复上述步骤，直到遍历完整个原链表。
-
返回反转后的链表的头节点
dummy.next。
对于单链表的翻转操作，需要遍历链表中的每个节点，时间复杂度为 O(n)O(n)O(n)，其中 nnn 是链表的长度。
空间复杂度上，因为只使用了常数级别的额外空间，所以空间复杂度为 O(1)O(1)O(1)。
92. 反转链表 II - 力扣（Leetcode）
给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。
示例 1：
输入： head = [1,2,3,4,5], left = 2, right = 4
输出： [1,4,3,2,5]
示例 2：
输入： head = [5], left = 1, right = 1
输出： [5]
提示：
- 链表中节点数目为
n 1 <= n <= 500-500 <= Node.val <= 5001 <= left <= right <= n
进阶： 你可以使用一趟扫描完成反转吗？
class Solution:
def reverseBetween(self, head,left: int, right: int):
dummy = ListNode()
flag = p = dummy
idx = 1
while head:
if left > idx:
p.next = head
head = head.next
p = p.next
flag = p
elif idx > right:
break
else:
nex = head.next
head.next = flag.next
flag.next = head
head = nex
if p.next:
p = p.next
idx += 1
p.next = head
return dummy.next
-
创建虚拟头结点 dummy，并将 flag 和 p 都指向它，这样在遍历链表时可以方便地将新的节点接到链表的尾部。
-
遍历链表，使用 idx 记录当前遍历的节点位置。
-
当 idx < left 时，说明还没有到达要翻转的区间，需要将当前节点接到 p 的后面，并将 p 和 head 分别向后移动一位。
-
当 idx >= left 且 idx <= right 时，说明已经到达要翻转的区间，需要将当前节点插入到 flag 节点后面，并将 flag 和 head 分别向后移动一位，同时更新 p 的位置，用于拼接翻转后的区间和未翻转的部分。
-
当 idx > right 时，说明已经遍历完了要翻转的区间，可以直接退出循环。
-
最后需要将未翻转的部分接到翻转后的区间的尾部。
-
返回虚拟头结点 dummy 的下一个节点，即翻转后的链表头节点。
需要注意几点：
-
需要引入一个 flag 指向翻转后的最后一个节点，用于拼接剩余节点。
-
翻转节点时需要使用 nex 暂存下一个节点，避免翻转后找不到下一个节点。
-
需要使用 p 保存当前遍历到的节点，用于拼接翻转后的区间和未翻转的部分。
时间复杂度为 O(n)，空间复杂度为 O(1)。
25. K 个一组翻转链表 - 力扣（Leetcode）
给你链表的头节点 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 <= 50000 <= Node.val <= 1000
进阶： 你可以设计一个只用 O(1) 额外内存空间的算法解决此问题吗？
class Solution:
def reverseKGroup(self, head, k):
# 计算链表长度
c = head
count = 0
while c:
count += 1
c = c.next
dummy = ListNode()
group = groupTail = dummy
# group记录每组翻转的开头
# groupTail记录每组结尾
p = head
while count>0:
if count>= k:
groupTail = p
for i in range(k):
nex = p.next
p.next = group.next
group.next = p
p = nex
group = groupTail
# 每组翻转之后将group移动到当前组的结尾，开始下一组翻转
else:
# 当剩余的数量少于k的时候不翻转
groupTail.next = p
count -= k
return dummy.next
使用一个指向虚拟头节点的指针来记录每个反转后的组的头节点。它使用一个指向虚拟头节点的指针来记录每个反转后的组的尾节点。在循环中，使用一个指向当前组头节点的指针来记录每个组的头节点，直到组中有足够的节点可以翻转。在翻转时，每个节点的next指针指向前一个节点，然后将当前组的头节点指向翻转后的第一个节点，更新虚拟头节点的下一个节点为翻转后的第一个节点。完成后，将group指针移动到当前组的尾节点，开始下一组的翻转。如果最后剩余的节点数量不足k个，则将它们留在原地。
以下是该解决方案的逐步说明：
-
首先计算链表的长度，并将其存储在变量count中。
-
初始化一个虚拟节点dummy，以及一个指向虚拟节点的指针group和groupTail，它们都指向dummy。
-
初始化一个指向链表头的指针p。
-
在循环中，只要count大于0，就进行迭代。
-
如果当前组中的节点数量不足k，则将剩余的节点留在原地，并更新groupTail的下一个指针。
-
否则，将groupTail指向p，并在循环中翻转当前组的前k个节点。
-
在循环中，使用指针nex来存储p的下一个节点，并将p的next指针指向group的下一个节点。然后将group的next指针指向p，更新p为nex。
-
翻转后，将group指针移动到当前组的尾节点groupTail，并开始下一组翻转。
-
在循环中，每次更新count的值。
-
返回虚拟头节点的下一个指针。
请注意，该解决方案的时间复杂度为O(n)，其中n是链表的长度。它的空间复杂度为O(1)。