How do I reverse only part of a linked list, between two positions?

Put a sentinel in front, dummy := &ListNode{Next: head}, so a range starting at position 1 needs no special case. Step left - 1 times from dummy to land on the node just before the range and call it before. Run the prev/current/next loop for exactly right - left + 1 nodes; when it stops, prev is the new front of the segment and current is the first node past it. Then before.Next.Next = current reattaches the old segment start, which is now its end, and before.Next = prev links in the new front. Return dummy.Next. For positions 2 to 4, [3 6 9 12 15] becomes [3 12 9 6 15].

How do I reverse a linked list in groups of k nodes in Go?

Count ahead first: if fewer than k nodes remain from where you stand, return them untouched. Otherwise flip exactly k nodes with the same loop, which leaves the block's original first node as its last, and set that node's Next to the result of handling the rest, either by recursing or by looping over a dummy node. A recursive helper only nests about n/k calls deep, and goroutine stacks grow anyway. For k = 2, [3 6 9 12 15] turns into [6 3 12 9 15], with 15 left last because it has no partner.

Can deep recursion crash a Go program here?

It can, just at a far greater depth than most runtimes allow. On 64-bit platforms a goroutine may grow its stack to 1,000,000,000 bytes by default, the figure debug.SetMaxStack hands back as the previous limit. Hitting that ceiling is not a panic: the runtime prints fatal error: stack overflow and exits, and recover cannot catch it. With the cap lowered through debug.SetMaxStack(1 << 20), a recursive reversal of 100,000 nodes ends exactly that way. The loop version keeps a constant stack and cannot hit it.

Why does reverseList return the new head instead of updating the caller's head?

Go passes every argument by value, so head inside the function is a copy of the caller's pointer. Assigning to it would only change that copy, and the caller would still hold the old first node, which after the reversal is the last node with a nil Next. Returning the new head and writing head = reverseList(head) at the call site is the idiomatic shape. A func reverseList(pp **ListNode) signature would also work, but it is rarely used for this.

Is there a built-in list type in Go I could reverse instead?

The standard library has container/list, a doubly linked list of *list.Element values holding any, but it offers no Reverse. You can still reverse one in place: walk from l.Front(), read e.Next() before moving anything, and call l.MoveToFront(e) on each element, so 3 6 9 12 15 comes out as 15 12 9 6 3 in O(n) time with O(1) extra space. If your values already sit in a slice, slices.Reverse flips it in place. Neither helps with a hand-built *ListNode chain, which is what this problem asks you to rewire.

Reverse a Linked List in Go (Golang): Iterative and Recursive

Q: Why does reverseList return the new head instead of updating the caller's head?

Go passes every argument by value, so head inside the function is a copy of the caller's pointer. Assigning to it would only change that copy, and the caller would still hold the old first node, which after the reversal is the last node with a nil Next. Returning the new head and writing head = reverseList(head) at the call site is the idiomatic shape. A func reverseList(pp **ListNode) signature would also work, but it is rarely used for this.

Q: Is there a built-in list type in Go I could reverse instead?

The standard library has container/list, a doubly linked list of *list.Element values holding any, but it offers no Reverse. You can still reverse one in place: walk from l.Front(), read e.Next() before moving anything, and call l.MoveToFront(e) on each element, so 3 6 9 12 15 comes out as 15 12 9 6 3 in O(n) time with O(1) extra space. If your values already sit in a slice, slices.Reverse flips it in place. Neither helps with a hand-built *ListNode chain, which is what this problem asks you to rewire.

reverse_list.go

Go 1.26

Not run yet

+ 7 hidden

Input

head = [3, 6, 9, 12, 15]

Expected

[15, 12, 9, 6, 3]

The old tail 15 becomes the new head, and the old head 3 now ends the list.