25. K 个一组翻转链表-一一网

给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。

k 是一个正整数，它的值小于或等于链表的长度。

如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

进阶：

你可以设计一个只使用常数额外空间的算法来解决此问题吗？
你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

输入：head = [1,2,3,4,5], k = 3
输出：[3,2,1,4,5]
复制代码

解法一

看答案之前，自己的写法。解法和两两交换链表中的节点类似，因为要求常数额外空间，就不能使用递归，所以使用迭代的解法。

主要思想：每次取出链表中的k个节点存在数组中，在数组中进行翻转节点的操作。

def reverseKGroup1(head, k):
    """迭代，解法和两两交换链表中的节点类似"""
    if k == 1: return head  # 如果k=1，就直接返回原链表

    dummy = ListNode()
    dummy.next = head  # 声明一个哑节点，指向链表的头节点
    temp = dummy  # 每次翻转temp后面的k个节点
    arr = []  # 用来记录链表中的节点

    while temp:
        for i in range(k):  # 每次取出链表中的k个节点
            arr.append(head)
            head = head.next
            if head is None: break  # 如果节点为空了，直接跳出这层for循环

        if len(arr) < k:  # 如果数组长度小于k，那么就不需要交换节点，直接跳出while循环
            break

        last_node = arr[-1].next  # 用来记录剩下的未交换的节点

        for i in range(k):  # 在数组中翻转节点
            if i == 0:  # 第一步让temp指向最后一个节点
                temp.next = arr[-1]
            arr[-i].next = arr[-(i + 1)]  # 翻转中间的节点，令后一个节点指向前一个节点
            if i == k - 1:  # 最后一步，让翻转后的最后一个节点指向剩下的未交换的节点
                arr[-(i + 1)].next = last_node

        temp = arr[0]  # 将temp指向交换过后的最后一个节点
        if temp.next is None: break  # 如果最后一个节点的next为空，则结束循环
        arr.clear()  # 每次循环结束后，清空数组，用于存储下次循环的k个节点

    return dummy.next
复制代码