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.
27 comments:
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
This code is quite good. I'm still unsure as to how it works, but it's exquisite.
Thanks for the appreciation. This code works - the fun is to know how... try a dry-run.
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;
}
Why cant we just swap elements from first - last
first + 1, last -1 till we reach the middle...
thats just n/2...
Im sorry...The above solution wont work n a sinle link list...
WTF was i thinking..
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
in java 1.6 u just use the descendingIterator method.
http://gotaninterviewcall.blogspot.com/
awsm
List reverse(LinkedList l) {
int size = l.size();
for(int i = 0; i < size; i++) {
l.add(i, l.removeLast());
}
return l;
}
static List reverse(LinkedList l) {
int size = l.size();
for(int i = 0; i < size; i++) {
l.add(i, l.removeLast());
}
return l;
}
Doesnt make sense unless you return the new first node.
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;
}
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.
Very nice. It was a little confusing at first but it's crystal clear now!
//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);
}
That java code is short and to the point
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;
}
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!
Woah, really cool idea!!
"... and to the point"
I see what you did there...
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
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;
}
really awsm algorithm. Great work.
Very neat solution. Thanks!
Post a Comment