Leetcode - 206. Reverse Linked List

Reversing a linked list is a common problem in coding interviews and data structures. In this blog, we'll discuss the approach, implementation, and time complexity of reversing a singly linked list. Approach A singly linked list consists of nodes where each node has two parts: Value/Data: The actual data stored in the node. Next Pointer: A reference to the next node in the list. To reverse a linked list, we need to modify the next pointer of each node so that it points to the previous node instead of the next one. Steps to Reverse a Linked List: Initialize Pointers: Start with two pointers: prev = null: This will become the new head at the end. curr = head: This will traverse the list. Iterate Through the List: Store curr.next in a temporary variable (temp) before changing it. Update curr.next to point to prev, effectively reversing the link. Move prev forward to curr. Move curr forward to temp. Return the New Head (prev). Code Implementation Here's the JavaScript implementation: var reverseList = function (head) { let prev = null; let curr = head; while (curr !== null) { let temp = curr.next; // Store the next node curr.next = prev; // Reverse the link prev = curr; // Move prev to current node curr = temp; // Move to next node } return prev; // New head of the reversed list }; Complexity Analysis Time Complexity: O(n) We traverse each node once, making the time complexity linear. Space Complexity: O(1) Since we are reversing the list in-place without using extra memory, the space complexity is constant. Example Input: 1 -> 2 -> 3 -> 4 -> 5 -> null Output: 5 -> 4 -> 3 -> 2 -> 1 -> null Summary Reversing a linked list is a fundamental operation that can be efficiently done using an iterative approach. By manipulating pointers, we can reverse the list in O(n) time and O(1) space. Mastering this technique is essential for tackling more complex linked list problems!

Apr 3, 2025 - 10:59

Reversing a linked list is a common problem in coding interviews and data structures. In this blog, we'll discuss the approach, implementation, and time complexity of reversing a singly linked list.

Approach

A singly linked list consists of nodes where each node has two parts:

Value/Data: The actual data stored in the node.
Next Pointer: A reference to the next node in the list.

To reverse a linked list, we need to modify the next pointer of each node so that it points to the previous node instead of the next one.

Steps to Reverse a Linked List:

Initialize Pointers: Start with two pointers:
- prev = null: This will become the new head at the end.
- curr = head: This will traverse the list.
Iterate Through the List:
- Store curr.next in a temporary variable (temp) before changing it.
- Update curr.next to point to prev, effectively reversing the link.
- Move prev forward to curr.
- Move curr forward to temp.
Return the New Head (prev).

Code Implementation

Here's the JavaScript implementation:

var reverseList = function (head) {
    let prev = null;
    let curr = head;

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

    return prev; // New head of the reversed list
};

Complexity Analysis

Time Complexity: O(n)
- We traverse each node once, making the time complexity linear.
Space Complexity: O(1)
- Since we are reversing the list in-place without using extra memory, the space complexity is constant.

Example

Input:

1 -> 2 -> 3 -> 4 -> 5 -> null

Output:

5 -> 4 -> 3 -> 2 -> 1 -> null

Summary

Reversing a linked list is a fundamental operation that can be efficiently done using an iterative approach. By manipulating pointers, we can reverse the list in O(n) time and O(1) space. Mastering this technique is essential for tackling more complex linked list problems!