Linked lists: Reversing a linked list

Data Structures
1

A recursive solution to the linked list reversion :slight_smile:

image
image960Ă—708 44.5 KB

2

I think it works, but for a non-trivial size, it would trigger a stack overflow since Java can only hold a limited number of recursive calls on the stack. This implementation requires that stack to be as large as the linked list which is probably not great.

For that reason alone I would only ever use an iterative approach for this problem. That being said, still a useful exercise. If you found a tail recursive solution, that would be slightly more useful since a future version of Java could implement tail recursion optimization which would collapse the stack when possible.

3

I used below approach to reverse the linked list. Appreciate if someone could indicate any problem with this approach. it works for datasets I have tested.

 public void reverse() {
        // original [10->20->30]
        // reverse  [10<-20<-30]
        int[] nodes = this.toArray();
        for(int i = 0; i < nodes.length; i++) {
            this.removeLast();
            this.addFirst(nodes[i]);
        }
    }
4

If I saw that answer in an interview I would be disappointed because you needed to create an auxiliary data structure that was a complete copy of all of the data in your existing data structure you were operating on (so any time that method is called it allocates O(n) space). It works, but I would never hire someone who could not do better.

Reversing a doubly linked list is quite straightforward so there is no need whatsoever to leverage an array like this. You need one or two temporary variables max, but nothing more.

Imagine it were a line of beans with arrows pointing from one bean to the next (in yellow) and previous (in blue) with a special green arrow pointing to the first bean and a special red arrow pointing to the last bean. You just gotta go through and flip the direction of all the yellow and blue arrows (and flip the green and red arrows to point to their counterpart). Think about what “flipping the arrows” would mean and make sure you keep track of any temporary variables you might need to hang onto while “flipping” through the list.

5

@jmrunkle Thank you for your feedback. Appreciate it.