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: []

Constraints:

• The number of nodes in the list is the range [0, 5000].

• -5000 <= Node.val <= 5000

Approach 1: Iterative

Similar to remove element from a linked list, we can traverse the list to solve the problem.

We iterate through a linked list using a current node variable. The concept involves updating the current node's reference to point to the previous one, effectively traversing the list. However, to avoid losing the reference to the previous node, we introduce an additional variable named prev. This variable stores the reference to the previous node.

Additionally, to ensure we don't lose the reference to the next node when moving from the current node to the next one, we introduce another variable named temp. This variable holds the reference of curr.next, allowing us to maintain continuity in the traversal process.

Steps

Step 1: Declare three variables: prev, curr, and temp

Step 2:

• prev would hold a reference to the node preceding the current node

• curr would hold a reference to the current node

• temp would hold a reference to the node following the current node (curr.next).

Step 3: Iterate through the list while curr is not null.

Step 4: Within the iteration:

• • Update temp to hold the reference to the next node (curr.next).

    • Update curr.next to point to the previous node (prev).

    • Update prev to be the current node (curr).

    • Update curr to be the next node (temp).

Step 5: After the iteration, return prev, which now holds the reference to the last node in the list.

/**
 * 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}
 */
const reverseList = function(head) {
    let prev = null;
    let curr = head;
    let temp = null;
    while (curr) {
        temp = curr.next;
        curr.next = prev;
        prev = curr;
        curr = temp;
    }
    return prev;
}

Approach2: Recursive

1. Base Case: If the current node is null (indicating the end of the list), return null.

2. Recursive Step: Recursively call the function on the next node (head.next).

3. Reverse the Pointers: Once the recursion reaches the end of the list, reverse the pointers. Set the next pointer of the current node's next node (head.next.next) to point back to the current node (head), effectively reversing the pointer.

4. Set Current Node's Next Pointer: Set the next pointer of the current node (head) to null, indicating the end of the reversed list.

5. Return New Head: Return the new head of the reversed list, which is the last node of the original list.

/**
 * 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) { 
    if (head === null || head.next === null) {
        return head;
        }

    let reversedListHead = reverseList(head.next);
    head.next.next = head; 
    head.next = null; 

    return reversedListHead;
}

Conclusion

Iterative Approach:

• Time Complexity: O(n)

• Space Complexity: O(1)

Recursive Approach:

• Time Complexity: O(n)

• Space Complexity: O(n)

Both methods have a time complexity of O(n) because they each visit every node in the list once. However, their space complexities differ:

• The iterative approach has a space complexity of O(1) because it only uses a constant amount of extra space, regardless of the size of the input list.

• The recursive approach has a space complexity of O(n) because it relies on the call stack, and the depth of the call stack corresponds to the length of the list, leading to linear space usage.