A linked list's nodes are reversed k at a time: the first k nodes are reversed, then the next k, and so on. If fewer than k nodes are left at the end, they stay in their order. (Solve it with real nodes and pointers, as an interview would ask.)
Input
The first line has n and k (1 ≤ k ≤ n ≤ 10⁴). The second line has the n values, from head to tail.
Output
The values after the change, separated by spaces.
Examples
Example 1 · Input
5 2 1 2 3 4 5
Expected output
2 1 4 3 5
Example 2 · Input
5 3 1 2 3 4 5
Expected output
3 2 1 4 5
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
Build the list from Node objects, then reverse k nodes at a time with prev, current and next.
Hint 2
A group shorter than k at the end stays as it is.
Hint 3
Connect each reversed group's tail to the next group's new head.
Solution
Show one correct solution (try it yourself first)
class Node:
def __init__(self, value, next=None):
self.value, self.next = value, next
n, k = map(int, input().split())
head = None
for v in reversed(input().split()):
head = Node(v, head)
dummy = Node(None, head)
before = dummy # the node in front of the next group
while True:
end = before
for _ in range(k):
end = end.next
if end is None:
break
if end is None:
break # fewer than k nodes left
first, after = before.next, end.next
prev, current = after, first # reverse first..end, pointing at what follows
while current is not after:
current.next, prev, current = prev, current, current.next
before.next = end
before = first
values = []
node = dummy.next
while node:
values.append(node.value)
node = node.next
print(*values)