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.