Reverse Linked List

Reversal means changing reference direction

To reverse a singly linked list, we do not need to create a second set of nodes. We can traverse the original chain and change each node's next so that it points backward to the already processed part instead of forward.

Three references hold the state

At every step we need three roles: current is the current node, previous is the part already reversed, and next temporarily preserves the remainder of the original chain.

Node previous = null;
Node current = head;

while (current != null) {
    Node next = current.next;
    current.next = previous;

    previous = current;
    current = next;
}

head = previous;

After assigning current.next, the old forward reference can no longer be obtained from the current node. That is why it is first saved in the local variable next. At the end, previous points to the former last node — the new head of the list.

Complexity

Every node is visited once, so the running time is O(n). The algorithm uses only a few references regardless of list size, so the additional space is O(1). The nodes themselves are not copied and their values are not changed.