Last Minute Notes
  • Github
  • Docs
  • Learn
    @sayanstwt
Lessons
0/15 done
  • Fast & Slow Pointers
  • In-Place List Reversal
Learn/Data Structures & Algorithms/Linked Lists

In-Place List Reversal

6 min Beginner 7 steps

Flip next pointers with prev, curr and next.

List
1 → ... → 5
Copy to array
O(n) space
Goal
O(1) space
null12345nullheadreverse it without copying the values anywhere
current visited done
In this lessonStep 1 of 7
  1. The problem
  2. Three refs
  3. One step
  4. Full run
  5. Save first
  6. Sublist
  7. Recap
Step 1 / 7problem

Reverse without copying

Reverse 1 → 2 → 3 → 4 → 5 using O(1) extra space, so copying into an array is out.

The nodes stay where they are. Only the next pointers change direction.

Key idea

Reversing a list means flipping every next pointer, one node at a time.

←→ step·R replay·Space pause

You'll learn

  • Reverse a list in place with prev, curr and next
  • Return prev as the new head
  • Save next before overwriting curr.next
  • Reverse a sublist with a dummy node and head insertion
Read the full notesArrays and Linked Lists, 7