25. Reverse Nodes in k-Group

【Description】

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.

【Idea】

相当于做子链表的逆置；
每次向前k个节点，截取该子链表做逆置
此处直接用空列表存储的对应链表值，reverse后再依次赋值。比较暴力

【Solution】

# 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:
        left = head
        right = left
        while True:
            tp_k = 0
            nums = []
            while tp_k < k and right != None:
                nums.append(right.val)
                right = right.next
                tp_k += 1
            if tp_k == k:
                nums.reverse()
                for i in range(len(nums)):    # 此处还可以写链表的逆置，就省去list[]的空间占用
                    left.val = nums[i]
                    left = left.next
            else:
                break
        return head