Reverse Linked List

Problem Statement

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

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

Example 2:
Input: head = [1,2]
Output: [2,1]

Example 3:
Input: head = []
Output: []

Approach: Iterative

We can reverse a linked list iteratively using three pointers: prev, curr, and next.

1. Initialize two pointers: prev as null and curr as head.
2. Iterate through the linked list as long as curr is not null:
   • Store the next node: next = curr.next. (We need to do this because we are about to break the link).
   • Reverse the current node’s pointer by pointing it to prev: curr.next = prev.
   • Move the prev pointer one step forward to the current node: prev = curr.
   • Move the curr pointer one step forward to the stored next node: curr = next.
3. When the loop finishes, curr will be null and prev will point to the last node of the original list, which is now the new head of our reversed list. Return prev.

Solution

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
function reverseList(head) {
    let prev = null;
    let curr = head;
    
    while (curr !== null) {
        let nextTemp = curr.next; // Store next node
        curr.next = prev;         // Reverse the link
        prev = curr;              // Move prev one step forward
        curr = nextTemp;          // Move curr one step forward
    }
    
    return prev;
}

Complexity Analysis

• Time Complexity: $O(n)$ where $n$ is the number of nodes in the linked list. We traverse the list exactly once.
• Space Complexity: $O(1)$. We only use a few pointers (prev, curr, nextTemp) regardless of the list size, which takes constant extra space.