Examples / Reverse a linked list▶Run in PyTrace

Reverse a Linked List – Python Visualization

Reversing a singly linked list in place means walking it once and turning every next arrow around. You need three references: prev (the already reversed part), curr (the node being processed) and nxt (so you don't lose the rest of the list when you overwrite curr.next).

It is a short function, but the order of the four assignments matters. PyTrace draws the nodes and arrows, so you can see the list split in two and the reversed half grow node by node.

ComplexityO(n) time, O(1) extra space.

Code

LeetCode 206: Reverse Linked List ↗

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        prev = None
        curr = head
        while curr:
            nxt = curr.next
            curr.next = prev
            prev = curr
            curr = nxt
        return prev

Inputs

LeetCode notation

head[1,2,3,4,5]

expected[5,4,3,2,1]

What to watch

The nodes and next arrows of the list, redrawn after each assignment
prev, curr and nxt pointing at nodes
The moment curr.next = prev flips an arrow

Reverse a Linked List – Python Visualization

Code

Inputs

What to watch

More algorithm visualizations