Sometimes you wish to reverse a Linked List.
Reversing the Singly Linked List with constant extra space is a little tricky matter.
This is a question generally asked in technical interviews as well :D
Here is a function for it.
public boolean reverse()
{
temp = head;
int i;
if(head.next!=null)
{
try
{
node<E> temp2=head.next;
node<E> temp3=head.next.next;
tail = head;
tail.next = null;
while(true)
{
temp2.next = head;
head = temp2;
if(temp3 != null) {temp2 = temp3;}
else {break;};
if(temp3.next !=null) {temp3 = temp3.next;}
else {temp3 = null;};
}
head = temp2;
return true;
}
catch(Exception e)
{
e.printStackTrace();
return false;
}
}
else
{
return true;
}
} Well, this function basically traverses the list viewing three nodes at a time and reverses the node.next member variable of the middle node. It reverses the list using O(1) extra space.These were all public methods exposed to the user for use. Now comes some private methods.These are not seen by the user but are required for the internal working of the class.
getNode(E elem) method is required to fetch the node element(first node element if multiple such nodes exists) of the Linked List which has element 'elem' same as the 'elem' passed as arguement.
Note: 'same as' means that true is returned when you call object1.equals(object2). More on this in my next post.
private node<E> getNode(E e)
{
temp = head;
boolean flag = false;
int i;
for (i=0; i<size-1 ; i++)
{
if (temp.elem.equals(e))
{
flag = true;
break;
}
temp = temp.next;
}
if(flag ==true)
{
return temp;
}
else
{
return null;
}
}
Sometimes for testing purpose, you need to print all the elements in the Linked List. I constructed a function for the same.
public void printAll()
{
temp = head;
int i;
//System.out.println("Call to Printall function initiated");
System.out.println();
//System.out.println("The first element is "+head.elem);
System.out.println("Size of the list is "+size);
for (i=0; i<size ; i++)
{
try
{
System.out.println(temp.elem);
}
catch (NullPointerException e)
{
e.printStackTrace();
System.out.println(i);
}
if (i!=size-1) temp = temp.next;
}
}
Now lets talk about a function which rarely comes into use but we you need it, you really really need it !!
This function returns an array of E type with elements which are in the list after the specified element (passed as arguement).
public E[] getRest(E e)
{
E[] temp_array=(E[])Array.newInstance(e.getClass(),remaining(e));
temp = this.getNode(e);
int i;
int array_index=0;
do
{
try
{
temp_array[array_index] = temp.elem;
}
catch (NullPointerException ex)
{
ex.printStackTrace();
//System.out.println(i);
}
array_index++;
//if (temp.next!=null) temp = temp.next;
}
while ((temp = temp.next) != null);
return temp_array;
} Note: The element passed as arguement is also included in the returned array. Note: For getRest(E e) function, you will need to import java.lang.reflect.Array in your code.
Note: This function generates a compiler warning as i am casting an object of 'Object' Class (newInstance returns an object of Object Class) into (E[]). This is also known as unchecked casts. It generates a compile time warning. But it is type safe so don't worry and go ahead.
In this function, I retrieved the Class Object associated with the elem e and then passed it along with the required size in the newInstance method of 'Array' class to create an array of the required type and size.
After that, I just traversed to the list assigning the required elements to the newly created array.
That is it.
You are done.
For the complete code, go here.
Do post your comments about the post.
