DSA Patterns (Multi-Lang)•Part 5: Linked Lists & Fast-Slow Pointers (37 - 45)
Reverse a Linked List.
In Simple Words:
Iterate with three pointers: prev = null, curr = head, next. Save curr.next, point curr.next = prev, advance prev = curr, curr = next. Return prev.
- Time: $O(N)$ | Space: $O(1)$
Multi-Language SolutionsPython 3 • JavaScript • TypeScript • Java • C++
Switch tabs or choose Allclass ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def reverseList(head: ListNode | None) -> ListNode | None:
prev = None
curr = head
while curr:
nxt = curr.next
curr.next = prev
prev = curr
curr = nxt
return prev