Reverse a linked list

Flip every next pointer so the list runs the other way, using three references and no extra memory.

Time O(n)Space O(1)Code C++, Python and C#

Watch it animatedStep through it, with the running line highlighted. Free with an account.

The idea

Walk the list once. At each node, remember where the list continues, point the node backwards at the previous one, then step forward.

Code

C++PythonC#

ListNode* reverseList(ListNode* head) {
    ListNode *prev = nullptr, *curr = head;
    while (curr) {
        ListNode* next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}

def reverse(head: ListNode | None) -> ListNode | None:
    prev, curr = None, head
    while curr:
        nxt = curr.next
        curr.next = prev
        prev = curr
        curr = nxt
    return prev

public static ListNode Reverse(ListNode head) {
    ListNode prev = null, curr = head;
    while (curr != null) {
        ListNode next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}

Tips

Save next before you overwrite curr.next, or the rest of the list is lost.
When the loop ends curr is null and prev is the new head.

In the .NET library

LinkedList<T> is doubly linked and hides its pointers, so interview problems use a hand-written ListNode class like the one on the overview page.