10. In-place Linked List Reversal

TL;DR

Reversing a linked list in place is a pointer reassignment dance: track previous, current, and next so you never lose the remainder of the list. The same core loop stops early and splices with a sentinel when reversing only a sublist (m..n) or k-sized blocks. Reorder list = find middle, reverse second half, merge alternating two iterators.

Recognition Cues

• Phrases: “reverse linked list,” “reverse between positions,” “reverse every k nodes,” “reorder L0 → L1 → … → Ln-1 → Ln to L0 → Ln → L1 → Ln-1 …,” “palindrome linked list” (often middle + reverse).
• Inputs: ListNode head, sometimes m, n, k.
• Outputs: new head or void (in-place).

Diagram

Pattern control flow (customize nodes for this pattern). camelCase node IDs.

Mental Model

Each step: next = current.Next, current.Next = previous, slide previous = current, current = next. For sublist, anchor a beforeStart node; after reversing the segment, wire beforeStart.Next to the new head and connect tail of segment to the rest. K-group: count k nodes; if a full group exists, reverse it as a block and recurse/iterate; partial remainder stays forward.

Generic Recipe

1. Full reverse: initialize previous = nil, current = head; while current, move next, flip link, advance previous / current; return previous as new head.
2. Sublist m..n: advance to node m-1 as beforeStart; reverse n-m+1 nodes using the loop; stitch beforeStart, new sub-head, and trailing tail.
3. K-group: walk while at least k nodes remain; reverse chunk; move head pointer for next chunk (often dummy node simplifies).
4. Reorder: slow/fast to middle; reverse second half; interleave first, second with careful next saves.
5. Always preserve next before overwriting current.Next.

Complexity

• Time: O(n) for full scan; sublist and k-group still linear per list length.
• Space: O(1) pointers; recursion for some k-group solutions is O(k) or O(n) stack — prefer iterative for strict O(1).

Generic Code Template

Go

package main

type ListNode struct {
	Val  int
	Next *ListNode
}

func reverseList(head *ListNode) *ListNode {
	var previous *ListNode
	current := head
	for current != nil {
		nextNode := current.Next
		current.Next = previous
		previous = current
		current = nextNode
	}
	return previous
}

func reverseBetween(head *ListNode, left int, right int) *ListNode {
	dummy := &ListNode{Next: head}
	beforeStart := dummy
	for index := 1; index < left; index++ {
		beforeStart = beforeStart.Next
	}
	subHead := beforeStart.Next
	var previous *ListNode
	current := subHead
	for index := 0; index <= right-left; index++ {
		nextNode := current.Next
		current.Next = previous
		previous = current
		current = nextNode
	}
	beforeStart.Next = previous
	subHead.Next = current
	return dummy.Next
}

func main() {
	list := &ListNode{Val: 1, Next: &ListNode{Val: 2, Next: &ListNode{Val: 3, Next: &ListNode{Val: 4, Next: &ListNode{Val: 5}}}}}
	_ = reverseList(list)
	again := &ListNode{Val: 1, Next: &ListNode{Val: 2, Next: &ListNode{Val: 3, Next: &ListNode{Val: 4, Next: &ListNode{Val: 5}}}}}
	_ = reverseBetween(again, 2, 4)
}

JavaScript

function reverseList(head) {
  let previous = null;
  let current = head;
  while (current !== null) {
    const nextNode = current.next;
    current.next = previous;
    previous = current;
    current = nextNode;
  }
  return previous;
}

function reverseBetween(head, left, right) {
  const dummy = { next: head };
  let beforeStart = dummy;
  for (let index = 1; index < left; index++) {
    beforeStart = beforeStart.next;
  }
  const subHead = beforeStart.next;
  let previous = null;
  let current = subHead;
  for (let index = 0; index <= right - left; index++) {
    const nextNode = current.next;
    current.next = previous;
    previous = current;
    current = nextNode;
  }
  beforeStart.next = previous;
  subHead.next = current;
  return dummy.next;
}

Variants

• Full reverse (206): classic three-pointer loop.
• Sublist reverse (92): dummy + reverse n-m+1 links.
• K-group reverse (25): count k, reverse if complete block else leave remainder.
• Reorder list (143): slow/fast middle, reverse second half, merge zig-zag.
• Palindrome (234): reverse half comparison.

Representative Problems

• 206. Reverse Linked List — full in-place reversal
• 92. Reverse Linked List II — reverse sublist between m and n
• 25. Reverse Nodes in k-Group — block reversal
• 143. Reorder List — middle, reverse, merge
• 234. Palindrome Linked List — half-reverse compare

Anti-patterns

• Losing the tail of the unreversed segment by not storing next before relinking.
• Off-by-one on left/right when using 1-based positions from the problem statement.
• Allocating new nodes when the problem demands O(1) extra space in-place reversal.
• K-group: reversing partial final group when the problem says leave remainder as-is — match the spec exactly.