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