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

这是一个迭代法翻转链表的实现，可以看作是对链表进行头插法的操作。它的具体实现思路如下：

1. 初始化一个空链表 dummy，作为反转后的链表的头节点。

2. 遍历原链表，每次取出当前节点 head，并将其后继节点 nex 保存下来。

3. 将 head 插入到 dummy 的后面，即 head.next = dummy.next，dummy.next = head。这样就把 head 放到了 dummy 的前面，相当于反转了链表的一部分。

4. 将当前节点移动到下一个节点，即 head = nex。

5. 重复上述步骤，直到遍历完整个原链表。

6. 返回反转后的链表的头节点 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 <= 500
• 1 <= 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

1. 创建虚拟头结点 dummy，并将 flag 和 p 都指向它，这样在遍历链表时可以方便地将新的节点接到链表的尾部。

2. 遍历链表，使用 idx 记录当前遍历的节点位置。

3. 当 idx < left 时，说明还没有到达要翻转的区间，需要将当前节点接到 p 的后面，并将 p 和 head 分别向后移动一位。

4. 当 idx >= left 且 idx <= right 时，说明已经到达要翻转的区间，需要将当前节点插入到 flag 节点后面，并将 flag 和 head 分别向后移动一位，同时更新 p 的位置，用于拼接翻转后的区间和未翻转的部分。

5. 当 idx > right 时，说明已经遍历完了要翻转的区间，可以直接退出循环。

6. 最后需要将未翻转的部分接到翻转后的区间的尾部。

7. 返回虚拟头结点 dummy 的下一个节点，即翻转后的链表头节点。

需要注意几点：

1. 需要引入一个 flag 指向翻转后的最后一个节点，用于拼接剩余节点。

2. 翻转节点时需要使用 nex 暂存下一个节点，避免翻转后找不到下一个节点。

3. 需要使用 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 <= 5000
• 0 <= 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个，则将它们留在原地。

以下是该解决方案的逐步说明：

1. 首先计算链表的长度，并将其存储在变量count中。

2. 初始化一个虚拟节点dummy，以及一个指向虚拟节点的指针group和groupTail，它们都指向dummy。

3. 初始化一个指向链表头的指针p。

4. 在循环中，只要count大于0，就进行迭代。

5. 如果当前组中的节点数量不足k，则将剩余的节点留在原地，并更新groupTail的下一个指针。

6. 否则，将groupTail指向p，并在循环中翻转当前组的前k个节点。

7. 在循环中，使用指针nex来存储p的下一个节点，并将p的next指针指向group的下一个节点。然后将group的next指针指向p，更新p为nex。

8. 翻转后，将group指针移动到当前组的尾节点groupTail，并开始下一组翻转。

9. 在循环中，每次更新count的值。

10. 返回虚拟头节点的下一个指针。

请注意，该解决方案的时间复杂度为O(n)，其中n是链表的长度。它的空间复杂度为O(1)。