Reverse a Linked List

"So you designed an algorithm that can sort integers in O(1) time? cool! But can you reverse a singly linked list?" - your interviewer

Reversing a linked list is one of those questions woes solution stares you on the face but it's a bit complex to code it.

Question: Given a single linked list, reverse it.

Let's go step by step on how one will solve it on paper physically.

Linked List:

Since if we reverse a linked list, the head will point towards end ie null.
1>Let's call that node prev.
2>Let's call the node we're currently on as curr for current
3>Since if we will point node's next towards a new node, we will lose its original next, let's call a node's original next as next.
Based on above our linked list looks like this :

Now point the curr's next to prev :

Now move prev to curr since for the next node the curr node will become prev:

And the next node becomes curr node, similar to initial condition:

Let's repeat the same process for all nodes.

At the end we return the prev pointer as the new head.

Now let's code it down as it is, step by step.

function reverseList(head) {
    var prev = null;                      // set prev to null
    while (head) {
        var next = head.next;             // set next as head's next 
        head.next = prev;                 // set pointer to prev
        prev = head;                      // move prev
        head = next;                      // move head
    }
    return prev;
}

And that's it! As a challenge implement the same recursively!

github : https://github.com/AKHILP96/Data-Structures-and-Algorithms/blob/master/problems/reverseLinkedList.js