IntermediateLinked Lists

In-place Reversal

Reverse entire list or sublists in-place without extra arrays

Time: O(n)
Space: O(1)
Pattern Overview

Core Idea

Iteratively reverse pointers, carefully managing previous/current/next and reconnecting borders.

When to Use

Use for full reversal, sublist [m,n] reversal, and reversing nodes in k-groups.

General Recognition Cues
General indicators that this pattern might be applicable
  • Reverse list/sublist
  • k-group reversal
  • O(1) extra space
Pattern Variants & Approaches
Different methodologies and implementations for this pattern
1

Reverse List

Classic iterative reversal

When to Use This Variant
  • Reverse whole list
Use Case
In-place reversal
Advantages
  • O(1) space
  • Linear time
Implementation
def reverse_list(head):
    prev, cur = None, head
    while cur:
      nxt = cur.next
      cur.next = prev
      prev, cur = cur, nxt
    return prev
2

Reverse Sublist

Reverse nodes between m and n

When to Use This Variant
  • Indices m..n
Use Case
Partial reversal
Advantages
  • Local change
  • No extra memory
Implementation
def reverse_between(head, m, n):
    if m == n: return head
    dummy = ListNode(0, head)
    prev = dummy
    for _ in range(m-1): prev = prev.next
    cur = prev.next
    for _ in range(n-m):
        nxt = cur.next
        cur.next = nxt.next
        nxt.next = prev.next
        prev.next = nxt
    return dummy.next
3

k-Group Reversal

Reverse nodes in groups of k

When to Use This Variant
  • Group size k
Use Case
Batch reversal
Advantages
  • Iterative or recursive
Implementation
def reverse_k_group(head, k):
    dummy = ListNode(0, head)
    group_prev = dummy
    while True:
        kth = group_prev
        for _ in range(k):
            kth = kth.next
            if not kth: return dummy.next
        group_next = kth.next
        # reverse group
        prev, cur = group_next, group_prev.next
        for _ in range(k):
            nxt = cur.next
            cur.next = prev
            prev, cur = cur, nxt
        tmp = group_prev.next
        group_prev.next = kth
        group_prev = tmp
Common Pitfalls
Watch out for these common mistakes
  • Lose next pointer
  • Reconnect borders wrong
  • k not multiple of length
Code Templates
Compare implementations across different languages
def template(*args, **kwargs):
    # General template placeholder
    pass
Example Problems
Classic LeetCode problems using this pattern
Complexity Analysis
Time Complexity
O(n)

Each link reversed once.

Space Complexity
O(1)

Constant pointers.

Ready to test your knowledge?

Test your pattern recognition with interactive questions