Reverse Nodes in k-Group
HardThe problem
Given the head of a linked list and a number k, reverse the nodes k at a time, from the front of the list, and return the new head. If fewer than k nodes are left at the end, leave them as they are. Rewire the nodes; do not just change their values.
- Example 1Input: head = [1, 2, 3, 4, 5], k = 2Output: [2, 1, 4, 3, 5]
Groups [1,2] and [3,4] are reversed. The last group [5] has fewer than 2 nodes, so it stays.
- Example 2Input: head = [1, 2, 3, 4, 5], k = 3Output: [3, 2, 1, 4, 5]
Only [1,2,3] is a full group. [4,5] is left alone.
- Example 3Input: head = [1, 2, 3], k = 1Output: [1, 2, 3]
Reversing groups of one changes nothing.
- 1 ≤ k ≤ number of nodes ≤ 5,000
- 0 ≤ node value ≤ 1,000
Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.
Try it here
Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.
Hints, one at a time
Nudge
Check there are k nodes ahead, reverse exactly those, then reconnect to the previous group.
The idea
For each group: confirm k nodes exist, reverse them in place, attach the group between the previous tail and the next group head.
Target: O(n) time, O(1) space
Go function shape
func reverseKGroup(head *ListNode, k int) *ListNodeReference solution
Tested with go test. Try it yourself first, then compare.
// ReverseKGroup reverses the list k nodes at a time; a final group shorter than k stays as it is.
func ReverseKGroup(head *ListNode, k int) *ListNode {
dummy := &ListNode{Next: head}
groupPrev := dummy
for {
kth := groupPrev
for i := 0; i < k && kth != nil; i++ {
kth = kth.Next
}
if kth == nil {
return dummy.Next // fewer than k nodes left
}
groupNext := kth.Next
prev, cur := groupNext, groupPrev.Next // reversing toward groupNext reconnects the group to the rest
for cur != groupNext {
cur.Next, prev, cur = prev, cur, cur.Next
}
oldFirst := groupPrev.Next // the old first node is now the group's tail
groupPrev.Next = kth
groupPrev = oldFirst
}
}