This week's book giveaway is in the Servlets forum.
We're giving away four copies of Murach's Java Servlets and JSP and have Joel Murach on-line!
See this thread for details.
The moose likes Beginning Java and the fly likes Reverse a Singly  linked list in java Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Murach's Java Servlets and JSP this week in the Servlets forum!
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "Reverse a Singly  linked list in java" Watch "Reverse a Singly  linked list in java" New topic
Author

Reverse a Singly linked list in java

Aditya Sirohi
Ranch Hand

Joined: Jan 05, 2010
Posts: 93

Hello Folks,

I was seeing a code online to reverse a linked list, but i could not understand what is happening. I tried to simulate this with a linked list 1-->2-->3-->4-->null, but could not figure it out. Can anyone explain me?

This is what i understood for input 1-->2-->3-->4-->null

while loops till the time current pointer reached to the end of the list, i.e null



Hunter McMillen
Ranch Hand

Joined: Mar 13, 2009
Posts: 492

If you kept track of the tail of the linkedlist you could simply create a new linked list by repeatedly unlinking the tail from the previous list.

Hunter


"If the facts don't fit the theory, get new facts" --Albert Einstein
Aditya Sirohi
Ranch Hand

Joined: Jan 05, 2010
Posts: 93

So the above code that uses recursion is fine?
Hunter McMillen
Ranch Hand

Joined: Mar 13, 2009
Posts: 492

well, is it reversing the linked list? I think you are trying to do too many things at once inside the while loop, try just changing the position of one node at a time.

Hunter
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 37950
    
  22
Beware of linked lists; you can suffer behaviour of a high level of complexity. Another way to do it is to put all the values onto a stack, then pop them in turn and add them back to the list.
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 37950
    
  22
What code that uses recursion?
Hunter McMillen
Ranch Hand

Joined: Mar 13, 2009
Posts: 492

None in this example. No need to include another data structure when you can just keep track of the tail. Less complex.

Hunter
Aditya Sirohi
Ranch Hand

Joined: Jan 05, 2010
Posts: 93

Nope the above code does not uses recursion, my bad. If i use a new Data structure like Stack it will use more memory. So the above code that i pasted is correct?

-Aditya
Hunter McMillen
Ranch Hand

Joined: Mar 13, 2009
Posts: 492

You tell us. Does it do what you intended it to do and reverse the list?

Hunter
fred rosenberger
lowercase baba
Bartender

Joined: Oct 02, 2003
Posts: 11153
    
  16

Aditya Sirohi wrote:So the above code that i pasted is correct?

The only way we could answer that question with any degree of certainty would be to compile, run, and test it - which is something YOU can do yourself, right? I would assume you already have it in a full working program. For one of us to test it, we'd have to write a bunch of code to drop this method into, which most people don't have the time to do.


There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors
Aditya Sirohi
Ranch Hand

Joined: Jan 05, 2010
Posts: 93

I did not implement this piece of code inside my class yet. I wanted to traverse through the code with an input in mind and trace the output on the white board first, so that i get a solid understanding before i implement it myself in the code.

-Aditya
 
It is sorta covered in the JavaRanch Style Guide.
 
subject: Reverse a Singly linked list in java
 
Similar Threads
Linked List Insertion and Deletion help
LinkedList
selection sort in a linked list
Java Linked List
nodes