Reverse Linked List — Practice

Problem

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

Examples

Example 1

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

Output: [5,4,3,2,1]

Constraints

•The number of nodes is in the range [0, 5000].
•-5000 <= Node.val <= 5000

Hints

Hint 1

Use three pointers: prev, curr, next — reverse curr's pointer to point at prev, then advance all three forward by one.

Hint 2

A recursive alternative reverses everything AFTER the current node first, then fixes up the current node's own pointers on the way back up the call stack — elegant, but costs O(n) stack space the iterative version avoids.

Solutions

public ListNode reverseList(ListNode head) {
    ListNode prev = null;
    ListNode curr = head;
    while (curr != null) {
        ListNode next = curr.next; // save next
        curr.next = prev;          // reverse pointer
        prev = curr;               // advance prev
        curr = next;               // advance curr
    }
    return prev; // prev is the new head
}

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