Linked List Reversal
O(n) SpaceO(1) Imagine a conga line. Everyone faces the person in front. To reverse, each person turns around and grabs the person who was behind them. You just need three things: who you’re looking at now, who was behind you, and who’s next. Process one person at a time and the whole line flips.
When to use it: Reversing a linked list (or a portion of it) is a building block for many problems: palindrome checking, reordering, reversing in k-groups, and more.
Key insight: You only need three pointers: prev, curr, and next. Save the next node, point curr backward, then advance. Repeat until done.
Common trap: Losing the reference to the rest of the list. Always save curr.next before overwriting it, or you’ll lose the rest of the chain.
function reverseLinkedList(head):
prev = null
curr = head
while curr != null:
next = curr.next # save next node
curr.next = prev # reverse the pointer
prev = curr # advance prev
curr = next # advance curr
return prev # prev is the new head
# Reverse nodes between positions left and right (1-indexed)
function reverseBetween(head, left, right):
dummy = new Node(0)
dummy.next = head
before = dummy
# Navigate to the node just before the reversal start
for i = 1 to left - 1:
before = before.next
# Reverse the sublist
prev = null
curr = before.next
for i = 0 to (right - left):
next = curr.next
curr.next = prev
prev = curr
curr = next
# Connect the reversed sublist back
before.next.next = curr # tail of reversed connects to remainder
before.next = prev # before connects to new head of reversed
return dummy.nextclass ListNode:
def __init__(self, val: int = 0, next: "ListNode | None" = None):
self.val = val
self.next = next
def reverse_linked_list(head: ListNode | None) -> ListNode | None:
prev = None
curr = head
while curr:
next_node = curr.next
curr.next = prev
prev = curr
curr = next_node
return prev
def reverse_between(head: ListNode | None, left: int, right: int) -> ListNode | None:
"""Reverse nodes between positions left and right (1-indexed)."""
dummy = ListNode(0, head)
before = dummy
for _ in range(left - 1):
before = before.next
prev = None
curr = before.next
for _ in range(right - left + 1):
next_node = curr.next
curr.next = prev
prev = curr
curr = next_node
before.next.next = curr
before.next = prev
return dummy.next
def reverse_k_group(head: ListNode | None, k: int) -> ListNode | None:
"""Reverse nodes in k-group. Remaining nodes stay as-is."""
# Check if there are k nodes remaining
check = head
for _ in range(k):
if not check:
return head
check = check.next
# Reverse k nodes
prev = None
curr = head
for _ in range(k):
next_node = curr.next
curr.next = prev
prev = curr
curr = next_node
# head is now the tail of the reversed group
head.next = reverse_k_group(curr, k)
return prevProblem: Given a singly linked list, determine if it is a palindrome using O(1) extra space.
How would you approach this?
Answer: This uses linked list reversal. Find the middle with slow/fast pointers, reverse the second half in-place, then compare both halves node by node. Reverse is the key building block.
Problem: Given a linked list, reverse nodes in groups of k. If the number of remaining nodes is less than k, leave them as-is.
How would you approach this?
Answer: This is iterative/recursive reversal in k-groups. Check if k nodes remain, reverse them using the standard three-pointer technique, then recursively handle the rest. Connect each reversed group to the next.
Time: O(n) because we visit each node exactly once, doing constant work per node (save, reverse pointer, advance).
Space: O(1) for the iterative version — only three pointer variables are needed. A recursive version uses O(n) stack space, which is usually not preferred for this problem.