How to reverse a singly linked list in Java ?

Sometimes the solutions are not quite obvious. Search for an algorithm to reverse a singly linked list using Java and you wont find any good hits except for this code.


public void reverse()
{
Node currentNode, nextNode, loopNode;
if(first==null)
return;

currentNode=first;
nextNode= first.next;
loopNode=null;


while(nextNode != null)
{
currentNode.next = loopNode;
loopNode= currentNode;
currentNode=nextNode;
nextNode =nextNode.next;
}

first = currentNode;
first.next = loopNode;

}

This might not be a very intuitive solution at first sight but infact this is a very clever simulation of C/C++ pointers in Java. Credit goes to my wife for this fascinating algorithm.

Another version of this algorithm can be found here. This is a much improved and efficient way of doing this.

Technorati tags: , ,

27 comments:

upnishad said...

If you are more into C or C++, I found another good resource:http://www.coders2020.com/how-do-you-reverse-a-singly-linked-list-how-do-you-reverse-a-doubly-linked-list-write-a-c-program-to-do-the-same

Anonymous said...

This code is quite good. I'm still unsure as to how it works, but it's exquisite.

upnishad said...

Thanks for the appreciation. This code works - the fun is to know how... try a dry-run.

Pat said...

Here is my solution with a single local variable and a LinkedList class:

class Node
{
public int data;
public Node next;
}

class LinkedList
{
public void reverseList()
{
Node cur = head;
head = null;
for (; cur != null; )
{
Node next = cur->next;
cur->next = head;
head = cur;
cur = next;
}
}

public Node head;
}

Digu said...

Why cant we just swap elements from first - last
first + 1, last -1 till we reach the middle...

thats just n/2...

Digu said...

Im sorry...The above solution wont work n a sinle link list...

WTF was i thinking..

Bragadeesh said...

Well, I too have come up with the same solution with comprehensiveness explaining with pictures. Can be found here.

http://technicalypto.blogspot.com/2010/01/java-program-to-reverse-singly-linked.html

Anonymous said...

in java 1.6 u just use the descendingIterator method.

Anonymous said...

http://gotaninterviewcall.blogspot.com/

bhuwan arora said...

awsm

Anonymous said...

List reverse(LinkedList l) {
int size = l.size();
for(int i = 0; i < size; i++) {
l.add(i, l.removeLast());
}
return l;
}

Anonymous said...

static List reverse(LinkedList l) {
int size = l.size();
for(int i = 0; i < size; i++) {
l.add(i, l.removeLast());
}
return l;
}

Anonymous said...

Doesnt make sense unless you return the new first node.

The Exception said...

public static Node reverse(Node head)
{
/*Handles the bad input case*/
if(head == null)
{
return head;
}

/*Makes sure it is valid to work with head.next*/
if(head.next == null)
{
return head;
}

/*grab what will become your tail reference on the way back*/
Node tail = head.next;

/*Traverse all the way to the end of the list and grab the last node
* this will become your new node*/
Node newHead = reverse(head.next);

/*Sets the tail to point to the node originally before tail*/
tail.next = head;

/*Set the tail reference to null or you'll get weird circular dependency*/
head.next = null;

return newHead;
}

PCSmasher said...

I see no one has commented on this in a while, well, it is still helping people out. I think.
As far as how it works, I think I have an idea. Take a linked list with three items (A, B, C, D).
Following the flow of the code,
if(first++null)
return; Since first is not null, continue on.

currentNode = A
nextNode= B
loopNode = null

Enter the while loop nextNode != null is true so
currentNode.next = null
loopNode = A
currentNode = B
nextNode = C

nextNode != null is true so
currentNode.next = A
loopNode = B
currentNode = C
nextNode = D

nextNode != null is true so
currentNode.next = B
loopNode = C
currentNode = D
nextNode = null (D is last on the list)

nextNode != null is false, exit loop
first = D
first.next = C

List is reversed.
Or at least that is how I interpret it. Being a rank newbie, I could be way off, if so, please let me know.

Thatoneguy said...

Very nice. It was a little confusing at first but it's crystal clear now!

Michael Somers said...

//3 liner below recursively print the list
Reverse(theList);

public static void Reverse(Elem e){
if (e!=null)
if(e.next !=null )
Reverse(e.next);
System.out.println(e.data);
}

Michael Somers said...
This comment has been removed by the author.
Michael Somers said...

That java code is short and to the point

Anonymous said...

public void reverse() {
Node previous = tail;
Node next = null;
for (Node current = head.next; current != tail; current = danach) {
next = jetzt.next;
current.next = previous;
previous = current;
}
head.next = previous;
}

Montag said...

Best solution, and easy to understand. You should put this as a KEY to understanding the algorithm. current becomes previous after the first run of the loop. That is key to the understanding. Thanks!

Matt314 said...

Woah, really cool idea!!

Anonymous said...

"... and to the point"

I see what you did there...

Anonymous said...

once your currentNode advance to the last node, then your nextNode will be null, then while loop end, and you are missing the last switch which is currendNode.next = loopNode

Anonymous said...

public void reverse() {
Node current = first;
Node newRoot;
newRoot = null;
while (current != null) {
Node tempNode = current.next;
current.next = newRoot;
newRoot = current;
current = tempNode;
}

first = newRoot;
}

Anonymous said...

really awsm algorithm. Great work.

Anonymous said...

Very neat solution. Thanks!