• Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

Reverse a Singly linked list in java

 
Aditya Sirohi
Ranch Hand
Posts: 93
Eclipse IDE Linux VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 492
Firefox Browser Linux VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
 
Aditya Sirohi
Ranch Hand
Posts: 93
Eclipse IDE Linux VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
So the above code that uses recursion is fine?
 
Hunter McMillen
Ranch Hand
Posts: 492
Firefox Browser Linux VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Pie
Posts: 50168
79
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Pie
Posts: 50168
79
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
What code that uses recursion?
 
Hunter McMillen
Ranch Hand
Posts: 492
Firefox Browser Linux VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 93
Eclipse IDE Linux VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 492
Firefox Browser Linux VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You tell us. Does it do what you intended it to do and reverse the list?

Hunter
 
fred rosenberger
lowercase baba
Bartender
Posts: 12196
35
Chrome Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Aditya Sirohi
Ranch Hand
Posts: 93
Eclipse IDE Linux VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic