Coding Interview Questions | Reverse a Linked List

December 30th, 2023

Reverse a Linked List Problem Introduction:

This summary will talk about my solution to the reversing a linked list problem as seen on leetcode here.

Reverse a Linked List Solution:

function reverseList(head: ListNode | null): ListNode | null {
  if (!head) {
    return null;
  }
  let headPtr = head;

  // Populate all values of the linked list,
  // requires O(n) time and space
  const nodeStack = [];
  while (headPtr) {
    nodeStack.push(headPtr.val);
    headPtr = headPtr.next;
  }

  headPtr = head;
  while (headPtr) {
    const reversedNodeVal = nodeStack.pop()!;
    headPtr.val = reversedNodeVal;
    headPtr = headPtr.next;
  }

  return head;
}

Reverse a Linked List Solution Summary:

Approach:

The solution above utilizes a two-pass approach to reverse a singly linked list. It first iterates through the list to populate a stack with node values, and then iterates again to update the linked list nodes with the reversed values.

Code Highlights:

1. Empty Linked List Check: First, the solution checks for an empty list and returns early if needed.
2. Stack Initialization: Then, we utilize a stack (nodeStack) to store values temporarily, requiring O(n) space.
3. List Traversal: Finally, we iterate through the list to update node values based on the reversed stack.

Overall, the solution requires O(n) time and space complexity.

Bonus Solution with O(1) Space Complexity:

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

  while (current !== null) {
    const nextNode = current.next;
    current.next = prev;
    prev = current;
    current = nextNode;
  }

  return prev;
}