Reverse Linked List

Reverse a singly linked list.

Example:
Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL
var reverseList = function(head) {
    //iterate through
    //keep track of prior and next
    //set next to prior, and move to next node
    let curr=head;
    let prev=null;
    let next=null;
    
    while (curr!=null) {
        next=curr.next; //keep track of next
        curr.next=prev; //set to prior
        prev=curr; //set new prev for next iteration
        curr=next; //move to next node
    }
    //return new head
    return prev; //since curr is null
};

Approach:
Read up on Linked Lists here (link to be added).
This is a fairly simple problem but one that comes up often. The gist of the strategy is to go through all the nodes in the linked list and reverse what it’s pointing to. However if you just do that, you’ll lose the connection between the nodes. For example, if you make the second node point to the first node, how do you get to the third node? The second node is no longer pointing to it.

So the key is to temporarily keep track of the “next” node in the chain as we move along the nodes in the linked list. We use two variables, prev and next, to keep track of the original prior and next nodes respectively, in the linked list.

At each iteration of the loop, we do the following:

  • keep track of the original next node by assigning it to next
  • set the node’s next pointer to the prior node, represented by prev
  • update prev to be the current node, since at next iteration it’ll be the prior node
  • move to next node

By the time we finish iterating, all the pointers have been reversed. We then return the new head of the linked list.