## 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.

## Solutions

### 0. 错误代码

要知道错在那里！

# 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:
return None
if k < 2:
stack = []
for _ in range(k):
if not node:
stack.append(node)
node = node.next
for _ in range(k-1):
new_node.next = stack.pop()
new_node = new_node.next

while node:
cur = node
for _ in range(k):
if not cur:
new_node.next = node
stack.append(cur)
cur = cur.next
new_cur = stack.pop()
cur_node = new_cur
for _ in range(k-1):
cur_node.next = stack.pop()
cur_node = cur_node.next
new_node.next = new_cur
new_node = new_node.next
node = cur
# Runtime: 32 ms
# [1,2,3,4,5]
# 2
# Output
# [2,1,4,5]
# Expected
# [2,1,4,3,5]


### 1. Recursion + Stack

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
return None
if k < 2:
stack = []
for _ in range(k):
if not node:
stack.append(node)
node = node.next
for _ in range(k-1):
new_node.next = stack.pop()
new_node = new_node.next
new_node.next = self.reverseKGroup(node, k)
# 81/81 cases passed (48 ms)
# Your runtime beats 75.41 % of python3 submissions
# Your memory usage beats 100 % of python3 submissions (13.7 MB)


### 2. Direct

反转硬刚。

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
if head is None or k < 2:

for i in range(k - 1):

tail = current
prev = None
for i in range(k):