Reverse A Singly Linked List

Q1) How to reverse a singly linked list efficiently?

Ans:

As I'm not sure how your linked list is represented internally, but maybe something like this will work:

Code:

currentFirstNode = end of list marker   
while there are more elements in the list   
   get next element 'e' in the list   
   link 'e' to currentFirstNode  (e.next = currentFirstNode)   
   currentFirstNode = 'e'  
end loop  
 

Q2) I would like to write an algorithm that can reverse singly Linked List without using any other type of data structures such as stacks, arrays, queue .... etc.

This algorithm have to be created only by using Linked List interface .

I've created one but the problem is that it's O(n^2), so how to writeg this algorithm to be O(n).

Ans:

This is the code of the singly linked list.

You just have to use this interfce to write the algorithm.

Code:

public class LinkList {
int size;
Node head;
Node tail;

public LinkList() {
size = 0;
head = null;
tail = null; }

public int size()
{
return size; 
}

public boolean isEmpty()
{
return (size==0); 
}

public void add(int x,String y)
{
Node n1 = new Node(x,y,null); 
if(size==0)
head = n1; 
else
tail.setNext(n1); 

tail = n1; 
size++;

 

public void Delete(int x)
{
if (x < 1 || x > size())
{
System.out.println(" index out of boundary ");
return; 
}
if (x==1)
{
Node n1 = head;
head = head.getNext();
n1.setNext(null);

}
else
{
Node n1 = head;
for(int i = 1; i< x-1; i++)
{
n1 = n1.getNext();
}
n1.setNext (n1.getNext().getNext());
n1.setNext(null);
}
size--;
}
}
 

Or
 

You can also use recursion to reverse the list:

public void reverse()
{ if (head == null || head.next == null) return;

Object p = removeFirst();
reverse();
addLast(p);
}
 

Assuming you have the methods for removing the first element and removing the last element (relatively straightforward to implement). 

public Object removeFirst()
{ if (head == null) throw NoSuchElementException();

Object p = head.data;
head = head.next;
return p;
}

public void addFirst(Object x)
{ Node p = new Node();
p.data = x;

// empty list
if (head == null)
head = last = p;

p.next = head;
head = p;
}

public void addLast(Object x)
{ // empty list
if (head == null) 
{ addFirst(x); }

Node p = new Node();
p.data = x;
last.next = p;
last = p;
}

Reversing non-recursively:

public void reverse()
{ Node p = head;
LinkList lst = new LinkList();

while (p != null)
{ Object x = removeFirst();
lst.addFirst(x);
p = p.next;
}

this = lst;
}

(Note: I'm not sure how you have your Node class setup)

Do you have a Java Problem?
Ask It in The Java Forum

Java Books
Java Certification, Programming, JavaBean and Object Oriented Reference Books

Return to : Java Programming Hints and Tips

All the site contents are Copyright © www.erpgreat.com and the content authors. All rights reserved.
All product names are trademarks of their respective companies.
The site www.erpgreat.com is not affiliated with or endorsed by any company listed at this site.
Every effort is made to ensure the content integrity.  Information used on this site is at your own risk.
 The content on this site may not be reproduced or redistributed without the express written permission of
www.erpgreat.com or the content authors.