JavaScript Challenge: Reverse a Linked List

posted by Jonah Dempcy

This article is a follow-up on my previous post on writing a linked list class in MooTools. In that post, I offered an implementation of a singly-linked list in JavaScript and gave a challenge: To reverse a linked list in place, starting with only a reference to the head. The challenge also forbade the use of storing the data externally -- that is to say, you can't just iterate over the linked list and stuff the items in a new array, then reverse the array.

As promised, here is my solution to the challenge. If you are planning on trying the challenge yourself, read no further.

I've included the code for defining the LinkedList and LinkedListItem classes as well. It's separate from my solution, so if you want to give it a try yourself, go ahead and copy the code below.

var LinkedList = new Class({

    // Input: Array collection
    // An array of items to turn into a singly linked list
    
    initialize: function(collection) {

        this.collection = new Array();
                   
        // Construct the linked list
        collection.each(function(item, i) {
            var item = new LinkedListItem(item);
            this.collection.push(item);
            
            if (i > 0) {
                this.collection[i - 1].setNext(item);
            }
        }.bind(this));
        
        this.setFirst(this.collection[0]);
    },
    
    // Input: LinkedListItem item
    // Sets the head to be the given item
        
    setFirst: function(item) {
        this.head = item;
    },
        
    // Returns: LinkedListItem head
    
    getFirst: function() {
        return this.head;
    },
    
    // Returns: Array result
    // An array with all items' values, in the order they are linked
    
    getAll: function() {
       var result = new Array();
       
       result.push(this.getFirst().getValue());
       
       var item = this.getFirst().getNext();
       while (item) {
           result.push(item.getValue());
           item = item.getNext();
       }
       
       return result;
    }
});

// This class defines an individual item in the linked list.
// The value it is instantiated with is stored in the value property,
// and is accessible via getter/setter methods.

var LinkedListItem = new Class({
    initialize: function(item) {
        this.value = item;
    },
    
    getNext: function() {
        return this.next;
    },
    
    setNext: function(item) {
        this.next = item;
    },
    
    getValue: function() {
        return this.value;
    }
});

For an in-depth discussion of this code including step-by-step commentary, check out the previous article, LinkedList Class in MooTools.

Reverse a Linked List: Solution

This is what I came up with:

window.addEvent('domready', function() {

    var list = new LinkedList(['a', 'b', 'c', 'd', 'e', 
                               'f', 'g', '1', '2', '3', 
                               '4', '5']);

    // Challenge: Reverse the linked list in place (list.collection) 
    //            without using another array

    // Input: LinkedList list

    function reverseLinkedList(list) {

        // Inputs: LinkedListItem item, LinkedListItem next
        //
        // Returns true if next item exists
        // If not, sets the head to be the existing item
        
        function checkForNextItem(item, next) {
            if (!$defined(next)) {
                list.setFirst(item);
                return false;
            } else {
                return true;
            }
        }
        
        // Our new tail is the old head
        var tail = list.getFirst(); // 0

        var itemOne = tail.getNext(); // 1

        // If there is only one element in the list, return it
        if (!$defined(itemOne)) {
            return list;
        }
        
        // Remove the old link from the tail
        tail.setNext(null);                      

       // Prepare third item variable for while() loop
        var itemThree = tail;
        
        // The while() loop will stop when the checkForNextItem() 
        // function fails to find a next item and calls 
        // list.setFirst() on the final existing item.
        
        while (list.getFirst() == tail) {
            
            itemTwo = itemOne.getNext(); // 2
            itemOne.setNext(itemThree); // link 1 to 0            
            if (!checkForNextItem(itemOne, itemTwo)) break;
                              
            itemThree = itemTwo.getNext(); // 3            
            itemTwo.setNext(itemOne); // link 2 to 1
            if (!checkForNextItem(itemTwo, itemThree)) break;
            
            itemOne = itemThree.getNext(); // 4
            itemThree.setNext(itemTwo); // link 3 to 2
            checkForNextItem(itemThree, itemOne);                       
            
        }
        
        return list.getAll();  
    }
    
    console.log('Forward: ' + list.getAll()); 
    console.log('Backward: ' + reverseLinkedList(list));
    
    // RESULT:
    //
    // Forward: a,b,c,d,e,f,g,1,2,3,4,5
    // Backward: 5,4,3,2,1,g,f,e,d,c,b,a    
});

The main part of the function that does the work of reversing the linked list is the while() loop. I use a helper method, checkForNextItem(), which is declared at the top.

You'll notice I declared the function inside the reverseLinkedList() function. The reason I did this is that checkForNextItem() is a private method that shouldn't be accessible to code outside of the scope of the reverseLinkedList() function. Just like declaring local variables when you don't need a global, you can declare private methods inside the scope of the function block. It's perfect for helper methods like this and it doesn't clutter the global namespace.

To explain what the checkForNextItem() actually does, let's examine the while() loop where it's used.

        while (list.getFirst() == tail) {
            itemTwo = itemOne.getNext();
            itemOne.setNext(itemThree);         
            if (!checkForNextItem(itemOne, itemTwo)) break;
                              
            itemThree = itemTwo.getNext();           
            itemTwo.setNext(itemOne);
            if (!checkForNextItem(itemTwo, itemThree)) break;
            
            itemOne = itemThree.getNext();
            itemThree.setNext(itemTwo);
            checkForNextItem(itemThree, itemOne);                              
        }

The while() loop continues until list.getFirst() no longer returns the tail (the old head). At that point, the loop knows to finish because the checkForNextItem() method, unable to find a next item, will set the head to be the final remaining item in the list. Thus, the old tail becomes the new head and the linked list is reversed.

The only other area of the code which warrants discussion is the check if there is only one item in the list, and calling setNext(null) on the new tail (the former head):

        // Our new tail is the old head
        var tail = list.getFirst(); // 0

        var itemOne = tail.getNext(); // 1

        // If there is only one element in the list, return it
        if (!$defined(itemOne)) {
            return list;
        }
        
        // Remove the old link from the tail
        tail.setNext(null);        

The check to make sure itemOne is defined is simply a fail-safe for linked lists with only one item. In that case, tail.getNext() will be undefined so we just return the list as it is, with only one item. Originally I wrote the check using the JavaScript typeof keyword (i.e. if (typeof itemOne == 'undefined')), but then I remembered to use MooTools' nifty $defined() method which is both more succinct and easier to read (in my opinion).

Besides the check for single-item lists, I also had to remove the old link from the tail (formerly the head). If you don't remove the link, the while() loop will never end, since the tail will link to the next-to-last item which links back to the tail, forever and ever. So that's why I call tail.setNext(null) there.

Refactoring the Code

After writing this, something just didn't feel right about the while() loop. It was messy and seemed to be doing the same thing 3 times. I remembered back to the first time I solved this challenge and recalled a more elegant solution. After changing the code, I ended up with this:

window.addEvent('domready', function() {
    var list = new LinkedList(['a', 'b', 'c', 'd', 'e', 
                               'f', 'g', '1', '2', '3', 
                               '4', '5']);


    // Input: LinkedList list
    // Returns: LinkedList list (reversed)

    function reverseLinkedList(list) {

        // Our new tail is the old head
        var current = list.getFirst(); // 0

        // If there is only one element in the list, return it
        if (!$defined(current.getNext())) {
            return list;
        }
                
        var previous = null;
        var next;       
        
        while (current != null) {
            next = current.getNext();
            current.setNext(previous);
            previous = current;
            current = next;        
        }
        list.setFirst(previous);
        
        return list;  
    }
    console.log('Forward: ' + list.getAll()); 
    console.log('Backward: ' + reverseLinkedList(list).getAll());
    
    // RESULT:
    //
    // Forward: a,b,c,d,e,f,g,1,2,3,4,5
    // Backward: 5,4,3,2,1,g,f,e,d,c,b,a    
});

This code is more optimized and nicer to read. It has the same functionality but the while() loop has been significantly simplified and the checkForNextItem() method has been eliminated altogether. It's a good thing when you can reduce complexity like that.

One other minor edit I made during refactoring was to change the function from returning list.getAll() to just returning the list itself. After thinking about it, I prefer for the input and outputs to both be of type LinkedList and then you can just call getAll() on the result. It's a minor nuance but worth pointing out.

Leave comments if you'd like a deeper explanation of a specific area of the code or if anything is unclear, and of course your own implementations are always welcome.