• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Devaka Cooray
  • Liutauras Vilda
  • Jeanne Boyarsky
  • Bear Bibeault
Sheriffs:
  • Paul Clapham
  • Knute Snortum
  • Rob Spoor
Saloon Keepers:
  • Tim Moores
  • Ron McLeod
  • Piet Souris
  • Stephan van Hulst
  • Carey Brown
Bartenders:
  • Tim Holloway
  • Frits Walraven
  • Ganesh Patekar

Reversing a LinkedList

 
Ranch Hand
Posts: 38
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi everyone,

I am trying to reverse a linked list, and am working in the IntNode class (we are not using the linkedlist wrapper class).

Here is my method:



My thought (in my head) was to simply take the passed in head argument of the list, put that into an integer array, then, copy the array backwards into a new list. The algorithm appears to work - logically, anyways - but when I try to print the linked-list that is returned from the listReverse method, I get "6, 4, 2", which was the original, unreversed, list.

Obviously I am missing some kind of fundamental logic error here.  To be clear, this exercise is not for marks, just for my own understanding of the material. Any help is appreciated!
 
Saloon Keeper
Posts: 3407
149
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
hi A,

it looks like your reverse method is working, but it is not. What is returned, cursor3, is the last element of the reversed list. That you see all elements of the reversed list is because of line 28, that prints all the produced elements.

What you must do in the reverse method, is to put the created head (cursor3, when j = array.length - 1) in a variable, and retaurn that when done.
 
A Axford
Ranch Hand
Posts: 38
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi,

thanks for the response!

I understand what you're saying now - how my list just returns the last element. However, when I amended my code to create a new head from cursor 3 I am still getting a similar issue.

 
Piet Souris
Saloon Keeper
Posts: 3407
149
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
In line 7 you overwrite cursor3 that you created in line 3. So, in line 5, start with j = array.length - 2 (but beware: your array might be only 1 in length!). And use some other name tha cursor3 in line 3!
 
Rancher
Posts: 460
6
IntelliJ IDE Spring Fedora
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
It's possible to reverse a linked list with constant space and only going through it one time.  
 
With a little knowledge, a cast iron skillet is non-stick and lasts a lifetime.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!