LeetCode-25. 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]

提示：
链表中的节点数目为 n
1 <= k <= n <= 5000
0 <= Node.val <= 1000

进阶：你可以设计一个只用 O(1) 额外内存空间的算法解决此问题吗？

解题思路一：重点是reversek。这里reversek需要理解的是这个函数的功能是翻转一个长度为k的链表。传入的参数是这k个节点的前一个节点start和后一个节点end。翻转之后前一个节点需要指向翻转后的第一个节点start.next = pre，翻转后的最后一个节点需要指向后一个节点first.next = cur。

1. 创建一个dummy node
2. 对链表以k为单位进行分组，记录每一组的起始和最后节点位置
3. 对每一组进行翻转，更换起始和最后的位置
4. 返回dummy.next.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reversek(self, start, end):
        pre, cur = start, start.next
        first = cur
        while cur != end:
            temp = cur.next
            cur.next = pre
            pre = cur
            cur = temp
        start.next = pre
        first.next = cur
        return first
    def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        if not head or k < 2:
            return head
        slow = dummy_head = ListNode(next = head)
        fast = head
        count = 0
        while fast:
            count += 1
            if count % k == 0:
                slow = self.reversek(slow, fast.next)
                fast = slow.next
            else:
                fast = fast.next
        return dummy_head.next

时间复杂度：O(n)
空间复杂度：O(1)

解题思路二：计数或者获取链表长度n，然后while循环都行。

# 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]:
        n = 0
        cur = head
        while cur:
            n += 1  # 统计节点个数
            cur = cur.next

        p0 = dummy = ListNode(next=head)
        pre = None
        cur = head
        while n >= k:
            n -= k
            for _ in range(k):  # 同 92 题
                nxt = cur.next
                cur.next = pre  # 每次循环只修改一个 next，方便大家理解
                pre = cur
                cur = nxt

            # 见视频
            nxt = p0.next
            nxt.next = cur
            p0.next = pre
            p0 = nxt
        return dummy.next

时间复杂度：O(n)
空间复杂度：O(1)

解题思路三：0

时间复杂度：O(n)
空间复杂度：O(n)