• 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
  • Liutauras Vilda
  • Jeanne Boyarsky
  • Devaka Cooray
  • Paul Clapham
Sheriffs:
  • Tim Cooke
  • Knute Snortum
  • Bear Bibeault
Saloon Keepers:
  • Ron McLeod
  • Tim Moores
  • Stephan van Hulst
  • Piet Souris
  • Ganesh Patekar
Bartenders:
  • Frits Walraven
  • Carey Brown
  • Tim Holloway

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: 3304
146
  • 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: 3304
146
  • 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!
 
Master Rancher
Posts: 451
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.  
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!