Java: Reverse Singly Linked List Inplace

This post is part of my ongoing Interview Guide where I post the problems I’ve faced and solutions I’ve come up with on my journey to land a software engineering role.

**Problem: **I have a singly linked list, but now need to reverse it. This means I need the tail to be the head and all the intermediate ptrs to “switch direction”. How can I do this?

**Solution: **

Before we can do anything, we need to better define the problem. basically, what we want to do is turn a list in form:

A* -> B -> C // * on node indicates head ptr

to:

A <- B <- C*

Code

You can look at my code on GitHub’s gist:

[[https://gist.github.com/SIRHAMY/2cc481beeff569283d98f03a1d6982cb](https://gist.github.com/SIRHAMY/2cc481beeff569283d98f03a1d6982cb)]

Explanation

Let’s walk through my solution.

On lines 12 – 14, we are initializing our variables:

• prev – > This holds  a pointer to the last node we traversed over. We need this pointer so we can correctly set the pointer of the next node we iterate to to this node. Looking at the example of the problem above may help. - Set to null
• next – > This holds the ptr of the node we will iterate to next. We need to explicitly store this value or else it would be overwritten when we reversed the direction of that particular node - Set to null
• curr -> This holds the ptr to the node we are currently modifying - Set to head

Lines 16 – 22 contain the algorithm logic

• Line 16: We’re iterating until curr is null. This won’t throw any null pointer errors because we check whether it’s null before we attempt to modify it.
• Line 17: First we’re saving a reference to the next Node in the original list. We do this so we can continue iterating through the list even after we’ve destroyed the original pointer (by reversing its direction).
• Line 18: We want to modify the curr Node’s pointer so that it is pointing the opposite direction it was originally. This means setting next equal to prev, which is the reference we’ve saved to the last Node we visited.
• Line 19: Once we’re done modifying the curr Node, we need to save a reference to it so that the next Node can set its next pointer to point to it. We do this by setting our prev variable equal to curr.
• Line 21: Now that we’ve saved the previous Node for use on the next iteration, we have to move curr forward so we aren’t stuck in an endless loop of modifying the same Node. We do this by setting curr equal to the reference for the next Node we saved on line 17.

Line 24 returns the last Node we modified, otherwise known as the new head of the list.