Description

Oftentimes you will have a node, next node pairing and need to reverse them.
?
Walk the list flipping each node's next to point backward, keeping prev / cur / next so you never lose the rest of the list.

Reach for when

You need to flip a linked list's direction. Can be used for any node, next node structure.

Runtime

O(n) time, O(1) space

Visualization

Pseudocode

prev = null
cur = head
while cur:
	next = cur.next    # save the rest before overwriting
	cur.next = prev    # flip this node's pointer backward
	prev = cur         # advance prev
	cur = next         # advance cur
return prev            # prev is the new head

Code

def reverse_list(head):
	prev = None
	cur = head
	while cur:
		nxt = cur.next      # save next
		cur.next = prev     # reverse the link
		prev = cur          # move prev forward
		cur = nxt           # move cur forward
	return prev             # new head