LeetCode 第 25 题：K 个一组翻转链表 Python 题解

本题解提供使用 Python 语言解决 LeetCode 上第 25 题“K 个一组翻转链表”的详细思路和代码实现。

问题描述：

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

示例：

输入：head = [1,2,3,4,5], k = 2
输出：[2,1,4,3,5]

解题思路：

1. 迭代翻转： 遍历链表，每次处理 k 个节点，将其翻转，并将翻转后的子链表连接到结果链表中。
2. 递归翻转： 递归处理链表，每次递归处理 k 个节点，将其翻转并返回翻转后的子链表头节点。

代码实现：

# 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: ListNode, k: int) -> ListNode:
        dummy = ListNode(0, head)
        groupPrev = dummy

        while True:
            kth = self.getKth(groupPrev, k)
            if not kth:
                break
            groupNext = kth.next

            # 翻转当前组
            prev, curr = kth.next, groupPrev.next
            while curr != groupNext:
                tmp = curr.next
                curr.next = prev
                prev = curr
                curr = tmp

            # 连接翻转后的组
            tmp = groupPrev.next
            groupPrev.next = prev
            groupPrev = tmp

        return dummy.next

    def getKth(self, curr, k):
        while k > 0 and curr:
            curr = curr.next
            k -= 1
        return curr

复杂度分析：

• 时间复杂度：O(N)，其中 N 是链表的长度。
• 空间复杂度：O(1)。