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

Input: head = [1, 2, 3, 4, 5]
Output: [5, 4, 3, 2, 1]

This problem is very similar to "Reverse String" problem, so it's natural to think of adapting that solution for Linked Lists. Unfortunately, traversing with two pointers doesn't work here because the right pointer should move to the left, and we cannot do that in a Linked List. The trick is actually in modifying the links of our Linked List to obtain its reversed version. How should we modify them?

We just have to reverse each link in the list. For example: 1 -> 2 -> 3 -> 4 should become 1 <- 2 <- 3 <- 4. And the head of the reversed list is the tail of the original one. How can we reverse these links?

One idea is to traverse the list from left to right using a variable node and convert each link node -> node.next to node.next -> node. In plain steps: start with node at the head; while node is not null, set nextNode to the node after node, make that next node point back at node, then move node forward to nextNode. But there is a problem with this algorithm. Can you find out what that is? Take some small example and run it by hand.

The problem is that the moment we reverse a link, we lose access to the next nodes. For example, if the list is 1 -> 2 -> 3. When node is 1, we reverse the link and the list becomes 1 <- 2 3. We lost the link between 2 and 3. And so at the next step node becomes 2 but node.next is 1 instead of 3. The solution is still good, but we need to implement it in such a way that this problem is fixed.

We should traverse the linked list, while using two pointers:

• prev - the previous node
• node - the current node

We will start with the first two nodes in the list: prev is the head and node is the node after the head. Then, for as long as node is not null, we will reverse the link prev -> node and update the two variables such that they point to the next two nodes. Can you figure out how to code this? Take the example above and figure out how you should update the pointers after each link reversal.

Start with prev at the head and node at the node after it. While node is not null:

• save the node after node in nextNode;
• make node point back at prev;
• move prev to node;
• move node to nextNode.

Don't forget to cut the old head's link to the second node, so the reversed list ends there, and return the new head.