Reverse Linked List

easy linked list pointers

Problem

Given the head of a singly linked list, reverse the list, and return the reversed list.

Input1 → 2 → 3 → null

Output3 → 2 → 1 → null

node values (comma-separated)

def reverse_list(head):
    prev, curr = None, head
    while curr is not None:
        nxt = curr.next
        curr.next = prev
        prev = curr
        curr = nxt
    return prev

function reverseList(head) {
  let prev = null;
  let curr = head;
  while (curr !== null) {
    const next = curr.next;
    curr.next = prev;
    prev = curr;
    curr = next;
  }
  return prev;
}

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
}

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

Explanation

In a linked list, each node points to the next one. To reverse the list we want every arrow to point the other way instead.

We walk through the list once with three helpers: prev (the part already reversed, starting empty), curr (the node we are on), and nxt (a temporary save of the next node).

At each node we do four small moves: remember nxt so we do not lose the rest of the list, flip curr's arrow to point back at prev, then slide prev and curr one step forward.

Saving nxt first is the important part — once we flip the arrow, the original forward link is gone, so we need that backup to keep moving.

When curr runs off the end, prev is sitting on the old last node, which is now the new head. Example: 1 → 2 → 3 becomes 3 → 2 → 1.

Time: O(n) Space: O(1)