Reverse Linked List: Inverting Node Connections

The "Reverse Linked List" problem is a classic algorithmic challenge, involving the reversal of a singly linked list.

Problem Statement

Given the head of a singly linked list, reverse the list and return the reversed list.

Example

Consider a linked list: 1 -> 2 -> 3 -> 4 -> 5 After reversing, the list becomes: 5 -> 4 -> 3 -> 2 -> 1

Iterative Solution

function reverseList(head) {
  let prev = null;
  let current = head;

  while (current !== null) {
    let nextTemp = current.next;
    current.next = prev;
    prev = current;
    current = nextTemp;
  }

  return prev; // New head of the reversed list
}

Breaking Down the Solution

• Initialize Pointers: Start with prev set to null and current set to the head of the list.
• Iterate Through List: Traverse the list, reversing the pointers at each node.
• Update Pointers: For each node, point it to the prev node, then update prev to be the current node and move current to the next node in the original list.
• Return New Head: At the end of the iteration, prev will be the new head of the reversed list.

Conclusion

The Reverse Linked List problem is a fundamental exercise in linked list manipulation, demonstrating the importance of pointer manipulation in data structures. It is a valuable skill for understanding more complex linked list operations and problems.