AI Hints
Home›DSA in Python Tutorial›Linked List Techniques
DSA in Python · Lesson 37 of 132

Reversing a Linked List

Flip every pointer.

⏱ 2 min read▶ Video at 42:53🎓 Free
Watch this lesson in the DSA in Python courseWatch on YouTube ↗Full DSA in Python course

Reversing a linked list is the most asked linked list question in interviews. The trick is to walk along the list once, and turn every arrow around as you go. Pause, and imagine the arrows flipping, one by one.

Reversing a Linked List
From the video: Reversing a Linked List
  • The most asked linked list question
  • Walk along once
  • Turn every arrow around

Three pointers

We keep three pointers. Previous starts as none. Current is the node we're working on. Before we flip current's arrow, we save the next node, so we don't lose the rest of the list. Then current points back to previous, and both pointers step forward. Run it. One, two, three, four, becomes four, three, two, one.

reverse_list.pypython
from node import build, show

def reverse(head):
    prev = None
    current = head
    while current:
        nxt = current.next
        current.next = prev
        prev = current
        current = nxt
    return prev

head = build([1, 2, 3, 4])
show(head)
show(reverse(head))
Output
1 -> 2 -> 3 -> 4 -> None
4 -> 3 -> 2 -> 1 -> None
Also uses node.py
class Node:
    def __init__(self, value, next=None):
        self.value = value
        self.next = next

def build(values):
    head = None
    for v in reversed(values):
        head = Node(v, head)
    return head

def show(head):
    vals = []
    while head:
        vals.append(str(head.value))
        head = head.next
    print(" -> ".join(vals) + " -> None")

Why it works

At every step, everything behind current is already reversed, and starts at previous. Everything ahead is untouched, and starts at next. When current falls off the end, previous is the new head. It's O of N time, and O of one extra space.

keyvalue
prevthe reversed part
currentthe node being flipped
nxtsaved, so we don't lose it
CostO(n) time, O(1) space

Summary

Save next, flip the arrow, step forward. Three pointers reverse a linked list in one pass. Next, a clever trick with two pointers moving at different speeds.

Key takeaways
  • Save next
  • Flip current.next
  • Return prev
Next up: Fast and Slow Pointers — the tortoise and the hare