DEV Community

Akhil
Akhil

Posted on

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:
Alt Text

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 :
Alt Text

Now point the curr's next to prev :
Alt Text

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

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

Let's repeat the same process for all nodes.

Alt Text

Alt Text

Alt Text

Alt Text

Alt Text

Alt Text

Alt Text

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

Alt Text

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;
}
Enter fullscreen mode Exit fullscreen mode

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

Discussion (1)