Leetcode 25/24 - Reverse Nodes in k-Group

题目描述

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->5

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

Given 1->2.

For k = 2, you should return: 2->1

For 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 = None

class 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)