Reverse Linked List in O(n) Time and O(1) Space using JavaScript

Note:

Your algorithm should run in O(n) time and use O(1) extra space.

## Problem Definition The task is to reverse a singly linked list. Given the head of the list, we need to reverse the list and return the new head. ### Input and Output Formats - **Input**: The head of a singly linked list. - **Output**: The head of the reversed singly linked list. ### Constraints and Assumptions - The list can contain any number of nodes, including zero. - The values in the nodes are integers. ### Example **Input**: `head = [1, 2, 3, 4, 5]` **Output**: `[5, 4, 3, 2, 1]` ## Understanding the Problem The core challenge is to reverse the direction of the links in the linked list. This problem is significant in many applications, such as undo functionality in software, reversing sequences, and more. ### Potential Pitfalls and Misconceptions - Simply reversing the values in the nodes is not sufficient; we need to reverse the links. - Care must be taken to not lose track of the nodes during the reversal process. ## Approach ### Naive Solution A naive approach might involve using additional space to store the nodes in an array and then reconstructing the list in reverse order. However, this would not meet the space complexity requirement of O(1). ### Optimized Solution We can reverse the linked list in-place using an iterative approach with three pointers: 1. **prev**: Points to the previous node. 2. **current**: Points to the current node. 3. **next**: Points to the next node. By iterating through the list and reversing the links, we can achieve the desired result. ### Thought Process 1. Initialize `prev` to `null` and `current` to `head`. 2. Iterate through the list: - Store the next node. - Reverse the link. - Move `prev` and `current` one step forward. 3. At the end of the iteration, `prev` will be the new head of the reversed list. ## Algorithm ### Step-by-Step Breakdown 1. Initialize `prev` to `null` and `current` to `head`. 2. While `current` is not `null`: - Store `current.next` in `next`. - Set `current.next` to `prev`. - Move `prev` to `current`. - Move `current` to `next`. 3. Return `prev` as the new head of the reversed list. ## Code Implementation

/**
 * 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}
 */
var reverseList = function(head) {
    // Initialize previous node to null
    let prev = null;
    // Initialize current node to head
    let current = head;
    
    // Iterate through the list
    while (current !== null) {
        // Store the next node
        let next = current.next;
        // Reverse the link
        current.next = prev;
        // Move prev and current one step forward
        prev = current;
        current = next;
    }
    
    // Return the new head of the reversed list
    return prev;
};

### Explanation of Key Parts - **Initialization**: `prev` is initialized to `null` because the new tail of the list will point to `null`. - **Iteration**: The loop continues until `current` becomes `null`, indicating the end of the list. - **Reversing the Link**: `current.next = prev` reverses the direction of the link. - **Updating Pointers**: `prev` and `current` are moved one step forward to continue the process. ## Complexity Analysis - **Time Complexity**: O(n), where n is the number of nodes in the list. Each node is visited exactly once. - **Space Complexity**: O(1), as no additional space proportional to the input size is used. ## Edge Cases - **Empty List**: If the list is empty (`head` is `null`), the function should return `null`. - **Single Node**: If the list contains only one node, the function should return that node as it is. ### Example of Edge Cases 1. **Empty List**: `head = null` **Output**: `null` 2. **Single Node**: `head = [1]` **Output**: `[1]` ## Testing To test the solution comprehensively, consider the following test cases: 1. A list with multiple nodes. 2. An empty list. 3. A list with a single node. 4. A list with duplicate values. ### Example Test Cases

// Test case 1: Multiple nodes
let head = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5)))));
console.log(reverseList(head)); // Output: [5, 4, 3, 2, 1]

// Test case 2: Empty list
head = null;
console.log(reverseList(head)); // Output: null

// Test case 3: Single node
head = new ListNode(1);
console.log(reverseList(head)); // Output: [1]

// Test case 4: Duplicate values
head = new ListNode(1, new ListNode(1, new ListNode(1)));
console.log(reverseList(head)); // Output: [1, 1, 1]

## Thinking and Problem-Solving Tips - **Understand the Problem**: Break down the problem into smaller parts and understand the requirements. - **Visualize**: Draw diagrams to visualize the linked list and the reversal process. - **Practice**: Solve similar problems to strengthen your understanding of linked lists and pointers. ## Conclusion Reversing a linked list is a fundamental problem that helps in understanding pointers and linked list manipulations. By practicing such problems, you can improve your problem-solving skills and gain a deeper understanding of data structures. ## Additional Resources - [LeetCode - Reverse Linked List](https://leetcode.com/problems/reverse-linked-list/) - [GeeksforGeeks - Reverse a Linked List](https://www.geeksforgeeks.org/reverse-a-linked-list/) - [YouTube - Reverse Linked List Tutorial](https://www.youtube.com/watch?v=O0By4Zq0OFc) By following this comprehensive guide, you should be able to understand and implement the solution to reverse a linked list efficiently. Happy coding!