0025._Reverse_Nodes_in_k-Group.md

25. Reverse Nodes in k-Group

难度: Hard

刷题内容

原题连接

• https://leetcode.com/problems/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 this linked list: 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.

解题方案

思路 1 - 时间复杂度: O(N)- 空间复杂度: O(1)******

可以递归操作, 有两种情况：

1. 就是压根没有k个node，那么我们直接保持这个k-group不动返回head
2. 如果有k个node的话，那么我们先找到第k个node之后的递归结果 node = nxt，然后反转前面k个node，让反转结果的结尾 tail.next = nxt

beats 92.70%

class Solution:
    def reverseKGroup(self, head, k):
        """
        :type head: ListNode
        :type k: int
        :rtype: ListNode
        """
        cur = head
        cnt = 0
        while cur and cnt != k: # 往后最多走k步
            cur = cur.next
            cnt += 1
        if cnt == k: # 如果当前 k-group 有 k 个node的话
            # 先找到第k个node之后的递归结果 node = nxt
            # 让反转结果的结尾 tail.next = nxt
            nxt = self.reverseKGroup(cur, k) 
            while cnt > 0: # 反转前面k个node
                tmp = head.next
                head.next = nxt
                nxt = head
                head = tmp
                cnt -= 1
            return nxt
        # 当前 k-group 压根没有k个node，那么我们直接保持这个k-group不动返回head
        return head

思路 2 - 时间复杂度: O(N)- 空间复杂度: O(1)******

迭代版本

贼难写，但是理清楚node之间的关系之后其实还是可以30分钟内写出来的

class Solution:
    def reverseKGroup(self, head, k):
        """
        :type head: ListNode
        :type k: int
        :rtype: ListNode
        """
        dummy = dummy2 = ListNode(0)
        dummy2.next = l = r = head

        while True:
            count = 0
            while r and count < k:   
                r = r.next
                count += 1
            if count == k:  
                pre, cur = r, l
                for _ in range(k): 
                    nxt = cur.next
                    cur.next = pre
                    pre = cur
                    cur = nxt
                # l = r
                dummy2.next = pre
                dummy2 = l
                l = r
            else:
                return dummy.next