To solve this problem, we need to reverse a singly linked list. The goal is to reverse the direction of the pointers in the list such that the last node becomes the first node, and the first node becomes the last node.

 

Approach

The approach involves iterating through the linked list while reversing the pointers of each node. Here’s a step-by-step breakdown:

1. Initialization: Start with two pointers, prev and current. The prev pointer is initialized to null because the new tail (originally the first node) should point to null after reversal. The current pointer starts at the head of the list.

2. Iteration: Traverse the list with the current pointer. For each node:

   • Store the next node: Temporarily store the next node of the current node to avoid losing the reference when we change the current node's pointer.

   • Reverse the pointer: Set the current node's next pointer to point to the prev node.

   • Move pointers forward: Update prev to be the current node and move current to the next node in the original list (which was stored earlier).

3. Termination: Once current becomes null, the prev pointer will be at the new head of the reversed list. Return prev.

This approach efficiently reverses the list in a single pass through the nodes with constant space complexity, making it optimal.

Solution Code

javascript

class ListNode {
  constructor(val = 0, next = null) {
    this.val = val;
    this.next = next;
  }
}

function reverseList(head) {
  let prev = null;
  let current = head;
  
  while (current !== null) {
    const nextTemp = current.next;
    current.next = prev;
    prev = current;
    current = nextTemp;
  }
  
  return prev;
}

// Debug your code below
let head = new ListNode(1, new ListNode(2));
let reversedHead = reverseList(head);
console.log(reversedHead.val);
console.log(reversedHead.next.val);

Explanation

• Initialization: The prev pointer starts as null because the first node of the original list will become the last node in the reversed list, pointing to null. The current pointer starts at the head of the list.

• Loop Through List: For each node, we:

  1. Store the next node (nextTemp) to remember the rest of the list.

  2. Reverse the current node's pointer to point to prev.

  3. Move prev to the current node and current to the next node (nextTemp).

• Termination: When current becomes null, prev will be pointing to the last node of the original list, which is now the head of the reversed list. We return prev as the new head.