Crack the Backend

Problem Statement

Given the head of a singly linked list, reverse the list and return the new head. The list has next pointers only; we must reverse the direction of the next pointers in place (or with O(1) extra space).

Empty list: return null. Single node: return that node. The classic approach is iterative with three pointers: prev, curr, and a saved next.

Key Observations

Iterative: Start with prev = null, curr = head. In each step: save next = curr.next, set curr.next = prev (reverse the link), then prev = curr, curr = next. When curr becomes null, prev is the new head. Each node is visited once; we only change next to point backward.
Recursive: Reverse the sublist head.next and get its new head; then set head.next.next = head and head.next = null. Return the new head of the reversed rest (which is the new overall head). Base: if head == null || head.next == null, return head.

Approach

High-level: prev = null, curr = head. While curr != null: next = curr.next, curr.next = prev, prev = curr, curr = next. Return prev.

Steps:

ListNode prev = null, curr = head. While curr != null: ListNode next = curr.next; curr.next = prev; prev = curr; curr = next.
Return prev.

Implementation

Java

public ListNode reverseList(ListNode head) {
    ListNode prev = null;

    while (head != null) {
        ListNode next = head.next;
        head.next = prev;
        prev = head;
        head = next;
    }

    return prev;
}

Test Cases

Example 1

Input

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

Expected

[5,4,3,2,1]

Explanation

Reversed.

Complexity Analysis

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

Follow-ups

Reverse linked list II: reverse only a sublist.