Short Bytes - Linked List Reversal

Introduction

Howdy. Thanks for stopping by. Today I'm going to write about reversing a Linked List, in the hopes of being able to explain it well enough to show myself I can understand it. Did you learn something here too? Let me know :) .

Why use this? What's the benefit?

What's the point you ask? Well... good question.

Performance wise, this should be an O(N) time complexity where N is the length of the list, and an O(1) space complexity as we're not taking up any more space in memory than was already taken by the original list.

I also do hear that this is a common interview question, and I guess this is to show you know what you're doing in the domain of Linked Lists and pointers. Besides... they're also just fun to write and get your head around!

With that said, let's dive right in.

Understanding this requires a twist of logical thinking:

Reversing a linked list is possible by some clever manipulation of the pointers in the list and variable reassignment. (More on pointers in another article, at some point!).

We have three variables to track in this case, which will allow us to do the manipulation we need:

Previous - A previous node, which we initialise as NULL.

Current - A current node, which we start at the head of the linked list - this.head.

Next - The next node, in this case, this.head.next.

In the case of a linked list with the values {1, 2, 3, 4, 5, NULL}. Let's leave off the boilerplate just for ease of understanding), this is how our initial variables would look:

Previous Current Next
Null 1 2

From here, it's a case of looping while the current node isn't NULL (ie, we haven't reached the end of the list), and updating the values as such:

Step 1: Next becomes Current.Next.
Step 2: Current.next becomes Previous.
Step 3: Previous becomes Current.
Step 4: Current becomes Next.

Step 5: Repeat until Current resolves to NULL.

Full step through - let's see what that looks like.

Note - arrows indicate an updated pointer, and between each iteration would be the check for a current node to confirm we haven't reached the end of a list.

**Previous**    **Current**    **Next** 
 Start Of Loop 
  NULL                1            2
    1     <-          2            2
    2     <-          3            3
    3     <-          4            4
    4     <-          5            5
    5     <-         Null         NULL
End Of Loop

Hopefully that clarifies how this goes. We're simply updating the values and pointers; flip the pointers update variables in the correct order, win. Simple, right? (Well.. yeah, once you know it! :) )

The final thing to do is to update the head to point at previous, therefore making this nicely reversed singly linked list start at what was previously the end of the list! Epic.

Here's a code example, for an in the wild:

reverse() {
        if(!this.head.next) {
            return this.printList(); 
        }
        let previous = null;  
        let current = this.head;  
        let next = null;  

        while(current) {
            next = current.next;  
            current.next = previous; 
            previous = current;
            current = next;    
        }
        this.head = previous; 
        return this.printList(); // does what it says on the tin.  
    }

Outro

Thanks for reading, if you got this far. I'm still learning, and actually learnt this as a part of some Udemy courses and further research on ol' Google. I'm starting to write technical articles to improve and cement my learning and skill development.

Did I make any glaring mistakes? Feel free to correct me, constructively, all appreciated.

Stay safe, stay awesome, stay healthy and code on!

Yours - theCodingBro