dsa / dsa-complexity
22 mins
DSA Module 4: Linked List Pointer Reversal
Why This Matters: Linked lists store non-contiguous nodes linked by memory pointers.
## Linked List Reversal
Manipulating node pointers in singly linked lists.
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def reverse_list(head: ListNode) -> ListNode:
prev = None
curr = head
while curr:
nxt = curr.next # Save next node
curr.next = prev # Flip pointer arrow
prev = curr # Advance prev
curr = nxt # Advance curr
return prev
```
MENTAL MODEL & MEMORY LAYOUT
POINTER REVERSAL STEP: [ Node 1 ] ──next──► [ Node 2 ] ──next──► [ Node 3 ] (After flip): [ Node 1 ] ◄──next── [ Node 2 ] ◄──next── [ Node 3 ]
COMMON PITFALLS TO AVOID
- Losing reference to `curr.next` before overwriting `curr.next = prev`.
Linked List Node Traversal
# prev = None, curr = head # Cycle through 3 pointers: prev, curr, nxt
Reverses singly linked list node directions in single O(N) pass.
CONCEPT MASTERY CHECKPOINT
Why must you save `nxt = curr.next` BEFORE assigning `curr.next = prev` during list reversal?
NEXT RECOMMENDED LESSON
DSA Module 5: Stacks, Queues & Monotonic Stack
Challenge: Reverse array representation of linked list.