Interview Prep: Reverse Linked List Algorithm

Welcome back to Interview Prep. Today we’ll look at a very popular interview question regarding linked lists.

If you already know the basics of linked lists, read on. If not, try starting with my “linked list basics” articles:

LINKED LISTS ARTICLES BASICS:
Linked Lists Basics Part I

Linked Lists Basics Part II

What’s the Question?

We’re given a linked linked list liked this:

This is a linked list with 5 nodes. Each node contains an integer 1-5. In this list, 1 points to 2. 2 points to 3. 3 points to 4, 4 points to 5. 1 is the “head” of the list and 5 is the “tail” of the list

Now, we want to reverse the links of the list so that it looks like one in green below

You see that in the picture above, our green linked list has been reversed. 5 is now the head and points to 4. 4 now points to 3 and so on. 0 is now the tail.

How to do it?

Well, you might guess that to reverse our original list it will involve each node’s “next” property. Yes, that’s right. The tricky part is that when we reverse a node’s “next” property and have it point to its previous node, we’ll lose reference to the former next node. Here’s what I mean:

Let’s just take another linked list. This time with just 3 nodes: 1, 2 and 3. We want to take 2’s “next” property and point it at “1”. Below I’ve circled in pink the arrow representing the “next” property we want to reverse

In the second line of the image above, I’ve 2’s “next” property to the previous member: “1”. However, as you can see, now there is no arrow pointing to “3”. “3” is now lost to our linked list.

So how do we avoid losing references when reversing a linked list?

Use Pointers

To illustrate what we’ll be doing, I’m going to use a picture and start in the middle of the list. It will be easier to visualize that way. (Yes, when we get to the real code we’ll start with the head of the list. Also for now, don’t worry about edge cases.)

Let’s go back to our original white linked list with 5 nodes:

You’ll notice I’ve added pointers in blue. P2, currently at node with the value of 3 is the main event!. We want to reverse its “next” property(represented as an arrow in our diagram). In order not to lose any references while we manipulate the “next” properties, we’ll set one more pointer: P1, which is currently at the node with the value of 2.

There are just 4 steps to solve this problem:

We still just one more pointer, a “P3” to point to the node after our “P2 node”.

We’ll set p3 to p2.next:

Set P2. next to its predecessor, “1”

Above, you’ll see in pink that I’ve reversed P2’s “next” property . P2 now points to P1, like we wanted.

So now what? How do we keep traversing the linked list?

We’ll have to keep moving the pointers. In fact there are just two more steps to go to finish the main logic!

Set P1 to P2:

Above, you’ll see I’ve shifted P1 to its new location

Last step: now set P2 to P3:

There you have one iteration of our traversal of our linked list.

Before we go to the code, however, I want to show you how P3 gets shifted:

We just did one complete iteration in steps 1-4 above. We’re now ready to start our second iteration. Let’s go back to just step one. In step one, we set P3 to P2.next like so:

You’ll remember we had already shifted P2 to P3’s position in step #4 above. Therefore, we can set a new P3 to the shifted P2’s next property.

Now to the Code

Just a reminder before we start coding.

That P2 pointer is our “star” pointer and our code will be constructed to accommodate it.

2)In our original linked list with 5 nodes, do you know what comes before “1” and after “5”. Yes, that right, NOTHING or “null”:

1. Also, since we’re not always sure how long our linked list will be, let’s use a “while” loop. We’ll keep looping until our “star” pointer, P2, runs off the list and gets to “null”

2. A minor point is, “what should this list return?” This is a good question to ask your interviewer. Maybe they don’t want anything returned! For now, let’s just return P1 ‘cause we can!

Ok, let’s code:

// Declare our function and pass it our linked list’s head // 
// node

const reverseLinkedList = head => {
      // our p2 is the star pointer.  Let’s 
set it to the head
     let p2 = head
    // p1 comes BEFORE P2.  But if p2 is the head,
   //  what can come before the head?  Must be “null”
    let p1 = null

  // Here’s our while loop.  We’ll keep looping 
 // so long as P2, our star, doesn’t fall off the linked list
// and get to “null”
    while ( p2 !== null) {
        let p3 = p2.next   //step 1
        p2.next = p1       //step 2
        p1 = p2              //step 3
        p2 = p3              //step 4
    }
    return p1          //This imaginary interviewer wanted
                               // me to return P1.  Go figure!
}

I should start adding a discussion of space and time complexity.

In this algorithm we have a time complexity of O(n) since we’re just traversing the list one time.

Space complexity is a cool O(1) since we’re doing all our operations in place. We’re not creating a new linked list or other object, for example, which would have taken up more space in memory.

And there you have a solution to a popular linked list interview question. Now you can knock ‘em dead!

Have fun and
Keep coding out your dreams!

Namaste!

Donny