Problem

Given a linked list, reverse the order of the nodes in the list.
For example, given the following list:
1 -> 2 -> 3 -> 4 -> 5
The output should be:
5 -> 4 -> 3 -> 2 -> 1
Input:
1 -> 2 -> 3 -> 4 -> 5
Output:
5 -> 4 -> 3 -> 2 -> 1

Solution

// Solution:
// The optimal solution is to use a stack to store the nodes in reverse order.
// Then, we can pop the nodes off the stack and add them to the end of the list.
// This solution is optimal because it only requires one pass through the list.
// It also only requires O(n) space, where n is the number of nodes in the list.

// Example:
// Input: 1 -> 2 -> 3 -> 4 -> 5
// Output: 5 -> 4 -> 3 -> 2 -> 1

// Time Complexity: O(n)
// Space Complexity: O(n)

function reverseList(head) {
  const stack = [];
  let current = head;

  while (current) {
    stack.push(current);
    current = current.next;
  }

  let newHead = stack.pop();
  current = newHead;

  while (stack.length) {
    current.next = stack.pop();
    current = current.next;
  }

  current.next = null;

  return newHead;
}