CODEWITHSUNDEEP
javalinked-list
Mel H
Mel H

Reputation: 21

reverse orderedLinkedList

I want my linked list which is in ascending order to be put in reverse. I start from the last node and insert the fist node after the last (which is now the head node) but I don't know why it is just not printing anything but going in an infinite loop. We're only allowed to use single linked list nodes and no iterator.

public void reverse1() 
{
    if (head == null) 
    {
        return;
    }
    Node p = head;
    Node t= last;
    while(p != null && head!=last)
    {

         t.next = p;
         t=p;
         p = p.next;   
    }
   head = p;
   isAscending = false;
}

(the last node i get from insert method and just setting the last node inserted as "last")

Upvotes: 2

Views: 75

Answers (3)

Tesseract
Tesseract

Reputation: 8139

Let's analyze your logic

t=p; - after this line t and p are equal

p = p.next; - since t=p this line is equivalent to p = t.next;

t.next = p; - since p = t.next; this line is the same as t.next = t.next;

This can't work. Try this instead

public void reverse1() {
  Node last = null;
  Node current = head;

  while(current != null) {
    Node next = current.next;
    current.next = last;
    last = current;
    current = next;
  }
}

edit:

Maybe you are supposed to use a recursive solution. Like this:

public void reverse1() {
  if(isEmpty()) return;
  Node head = removeHead();
  reverse1();
  add(head);
}

Here I assume that removeHead() returns the head and also removes it from the list. And that add() will add a node at the end.

Upvotes: 1

radically
radically

Reputation: 56

You're creating a circular linked-list with your code by not setting the next pointer of the new tail to be null. It seems what you should do is check if the "next" of the current pointer is the old head, set p.next = null then break out of the loop

Upvotes: 0

orestiss
orestiss

Reputation: 2283

I believe that when you do t.next = p you create a loop from the ending node to the beginning, and that creates the infinite loop.

You can print your list in reverse with recursion if you are interested only in printing.

And maybe you can change the pointers to create the reverse list with recursion also, I have never done this though...

Upvotes: 0

Related Questions