AI solution for JavaScript Coding Question on BFE.dev
47. reverse a linked list

Solution:

To reverse a linked list, we need to modify the next property of each node to point to the previous node instead of the next node. We also need to keep track of the current node, previous node, and next node while iterating through the list.

Here's how we can do it iteratively:

function reverseLinkedList(head: Node): Node {
  let current = head;
  let previous = null;
  while (current) {
    const next = current.next;
    current.next = previous;
    previous = current;
    current = next;
  }
  return previous;
}

We start with the head node and initialize current to it and previous to null. We set up a loop, where we first save the reference to the next node in next. Then we modify the next property of current to point to previous. This effectively reverses the direction of the link. Then we update previous to current and current to next. We continue this loop until we reach the end of the list.

At the end, previous will be the new head of the reversed list, so we return it.

Here's how we can do it recursively:

function reverseLinkedList(head: Node): Node {
  if (!head || !head.next) {
    return head;
  }
  const reversed = reverseLinkedList(head.next);
  head.next.next = head;
  head.next = null;
  return reversed;
}

We start by checking if the input head is null or if it's the last node in the list. In either case, we return head.

Otherwise, we recursively call reverseLinkedList on the next node, which returns the reversed list starting from that node (reversed).

We then modify the next property of the next node (previously the current node) to point to head, effectively reversing the link between the two nodes.

Finally, we set the next property of head to null to complete the reversal, and return reversed, which is now the new head of the reversed list.

Note that for the recursive solution, we need to make sure that we are returning the new head of the list after the last recursion. This happens when we get to the end of the original list and start wrapping back up the stack of recursive calls.