Linked Lists Reversing and rewiring
304. Reverse Nodes in k-Group
You are given head, the first node of a singly linked list, and an integer k. Split the list into groups
of k nodes, counting from the head: the first k nodes, then the next k, and so on. Reverse the order of
the nodes inside each full group, and return the head of the new list.
When the number of nodes is not a multiple of k, the last group has fewer than k nodes. Leave those nodes
as they are, in their original order.
Move the nodes by changing their next pointers. Do not change the value in any node, and do not create new
nodes.
The examples write a list as its values from the head on, so head = [4,1,6] is the list 4 → 1 → 6. The
output shows the node you return the same way, as the list from that node on.
Example 1
Input: head = [7, 2, 9, 4, 1, 8, 6, 3], k = 3
[9,2,7,8,1,4,6,3]Explanation: The first two groups are 7, 2, 9 and 4, 1, 8, and each one is reversed. The last two nodes, 6 and 3, are fewer than 3, so they stay in their order at the end.
Example 2
Input: head = [10, 20, 30, 40, 50, 60], k = 2
[20,10,40,30,60,50]Explanation: Six nodes make three full groups of two, so no node is left over. The two nodes of each group swap places.
Example 3
Input: head = [-2, 0, 8, -9], k = 4
[-9,8,0,-2]Explanation: k equals the number of nodes, so the whole list is one group, and the answer is the whole list
reversed.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
1 ≤ number of nodes ≤ 105-109 ≤ Node.val ≤ 1091 ≤ k ≤ number of nodes
Clarifying questions
What you would ask an interviewer before writing any code.