Big O Gym › Problem

Big O Practice: Reverse Linked List

Time and space complexity practice in Python and JavaScript. Concept tested: in-place pointer reversal.

def reverse_list(head):
    prev = None
    cur = head
    while cur:
        nxt = cur.next
        cur.next = prev
        prev = cur
        cur = nxt
    return prev

Variables

  • n - number of nodes in the list

Explanation

Single traversal flipping each pointer - **O(n)** time. Three reused locals, **O(1)** space. The recursive form uses O(n) stack and is sometimes accepted; this iterative form is canonical.

More Big O practice problems · Today's daily problem