本文共 3650 字，大约阅读时间需要 12 分钟。

题目描述

Leetcode 24 题主要考察的链表的反转，而 25 题是 24 的拓展版，加上对递归的考察。

对题目做一下概述：

提供一个链表，给定一个正整数 k, 每 k 个节点一组进行翻转，最后返回翻转后的新链表。

k 的值小于或等于链表的长度，如果节点总数不是 k 的整数倍，将最后一组剩余的节点保持原有顺序。

注意：

• 算法只能使用常数的空间
• 不能单纯的改变节点内部的值，需要进行节点交换。

举例：

Example:Given 1->2->3->4->5.For k = 2, you should return: 2->1->4->3->5For k = 3, you should return: 3->2->1->4->5Given 1->2.For k = 2, you should return: 2->1For k = 3, you should return: 1->2

解题思路

主要考察来了我们对链表的反转已经递归思想的熟悉度。

对链表反转时，可以借助三个指针，pre，current，next

• pre 表示被翻转节点的前一个节点
• current 表示正在被翻转的节点
• next 表示正在被翻转的下一个节点

每次翻转时：

• next 指向 current 的下一个
• current 的 next 指向 prev
• 同时 current 和 prev 向前一步

在每次翻转后：

• current 表示下一个需要被翻转组中的第一个节点
• prev 表示当前翻转后的新链表头
• 原来的头 head 成了被翻转组中的尾节点

递归的处理

首先看到 K 个一组，想到到局部处理，并且局部处理翻转的方式是一致的，自然联想到递归。

递归的出口就是，被翻转后的新链表头或者未满足条件无需翻转的链表头。

代码实现：

# Question: Reverse Nodes in k-Group# Given a linked list, reverse the nodes of a linked list k at a time and# return its modified list.## k is a positive integer and is less than or equal to the length of the linked# list. If the number of nodes is not a multiple of k then left-out nodes in the# end should remain as it is.# Example:# Given 1->2->3->4->5.# For k = 2, you should return: 2->1->4->3->5# For k = 3, you should return: 3->2->1->4->5# Note:# Only constant extra memory is allowed.# You may not alter the values in the list's nodes, only nodes itself# may be changed.# Definition for singly-linked list.class ListNode:    def __init__(self, x):        self.val = x        self.next = Noneclass Solution:    def reverseKGroup(self, head: ListNode, k: int) -> ListNode:        # check if head is NULL List        if head is None or head.next is None:            return head        # get the number of nodes        list_length = 0        new_head = head        while new_head is not None:            list_length += 1            new_head = new_head.next        # If the length of nodes is less than the number of group        if list_length < k:            return head        # calculate the number of groups that can be reversed        number_of_groups = int(list_length / k)        return self.swapPairs(head, k, number_of_groups)    def swapPairs(self, head: ListNode, k, number_of_groups, number_of_reversed_groups=0) -> ListNode:        prev = None        current = head        n = k        # reverse the node due to the count of n        # After the reversal is completed，        # prev is the new head of the group that has been reversed.        # current points the head of the next group to be processed.        # head is the new end of the group that has been reversed.        while current and n > 0:            n -= 1            next = current.next            current.next = prev            prev = current            current = next        # after a group of nodes is reversed, then increase 1.        number_of_reversed_groups += 1        # determine whether to reverse the next group        if current is not None and number_of_reversed_groups < number_of_groups:            head.next = self.swapPairs(                current, k, number_of_groups, number_of_reversed_groups)        else:            head.next = current        return prev    def print_list_node(self, head: ListNode):        result = ''        while head is not None:            result += str(head.val) + '->'            head = head.next        print(result.rstrip('->'))if __name__ == '__main__':    l1 = ListNode(1)    l2 = ListNode(2)    l3 = ListNode(3)    l4 = ListNode(4)    l5 = ListNode(5)    l1.next = l2    l2.next = l3    l3.next = l4    l4.next = l5    solution = Solution()    solution.print_list_node(l1)    reversed_l1 = solution.reverseKGroup(l1, 2)    solution.print_list_node(reversed_l1)

转载地址：http://zhqyz.baihongyu.com/