Reverse Linked List easy

Problem Statement

Reverse a singly linked 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: []

Steps

1. Initialization: We'll use three pointers: prev, curr, and next. prev will point to the previous node (initially null), curr will point to the current node (initially the head), and next will temporarily store the next node.

2. Iteration: We iterate through the linked list, reversing the links as we go.

3. Reversal: In each iteration:

   • We store the curr.next in next to save it for later.
   • We change the curr.next to point to prev. This reverses the link.
   • We move prev one step forward to curr.
   • We move curr one step forward to next.

4. Termination: The iteration continues until curr becomes null, indicating we've reached the end of the list.

5. Return: The prev pointer now points to the new head of the reversed linked list.

Explanation

The algorithm works by iteratively changing the direction of the links in the linked list. Imagine you have nodes A -> B -> C. The algorithm first reverses the link between A and B, making it A <- B. Then, it moves to node B and reverses the link between B and C, making it A <- B <- C. This process continues until all the links are reversed.

Code

class ListNode {
    val: number;
    next: ListNode | null;
    constructor(val?: number, next?: ListNode | null) {
        this.val = (val===undefined ? 0 : val)
        this.next = (next===undefined ? null : next)
    }
}

function reverseList(head: ListNode | null): ListNode | null {
    let prev: ListNode | null = null;
    let curr: ListNode | null = head;
    let next: ListNode | null = null;

    while (curr !== null) {
        next = curr.next; // Store the next node
        curr.next = prev; // Reverse the link
        prev = curr;      // Move prev forward
        curr = next;      // Move curr forward
    }

    return prev; // prev now points to the new head
}


// Example usage:
const head = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5)))));
const reversedHead = reverseList(head);

let current = reversedHead;
let reversedListValues: number[] = [];
while (current !== null) {
    reversedListValues.push(current.val);
    current = current.next;
}

console.log(reversedListValues); // Output: [5, 4, 3, 2, 1]

Complexity

• Time Complexity: O(N), where N is the number of nodes in the linked list. We iterate through the list once.
• Space Complexity: O(1). We use a constant number of extra variables (prev, curr, next).