ISourceCode

Make the frequent cases fast and the rare case correct

Algorithm to Reverse a Linked List

This is an implementation to reverse the elements of a linked list.

I have used the explanation and snippet from this course notes

In this method no new storage is required.

Please refer the notes for a clear understanding.

There are other approaches to solve this, for example recursion or by moving nodes. In this case reference to nodes are reassigned.

class Node
{
	public int item;
	public Node next;
	public Node(int val)
	{
		item = val;
	}
	public void displayNode()
	{
		System.out.println("[" + item + "] ");
	}
} 
class LinkedList
{
	private Node first;
	public LinkedList()
	{
		first = null;
	}
	public boolean isEmpty()
	{
		return (first==null);
	}
	public void insert(int val)//inserts at beginning of list
	{
		Node newNode = new Node(val);
		newNode.next = first;
		first = newNode;
	}
	public Node delete()//deletes at beginning of list
	{
		Node temp = first;
		first = first.next;
		return temp;
	}
	public void display()
	{
		System.out.println("List items from first to last :");
		Node current = first;
		while(current != null)
		{
			current.displayNode();
			current = current.next; 
		}
		System.out.println("");
	}
	public void reverse() 
	{
		Node current = first;
    		first = null;
    		while (current != null) 
		{
		        Node save = current;
		        current = current.next;
		        save.next = first;
		        first = save;
		}
	}
	public Node search(int val)
	{
		Node current = first;
		while(current.item != val)
		{
			if(current.next == null)
				return null;
			else
				current = current.next;
		}
		return current;
	}
	public Node delete(int val)
	{
		Node current = first;
		Node previous = first;
		while(current.item != val)
		{
			if(current.next == null)
				return null;
			else
			{
				previous = current;
				current = current.next;
			}
		}
		if(current == first)
			first = first.next;
		else
			previous.next = current.next;
		return current;
	}

	
} 
class LinkedListBlog
{
	public static void main(String[] args)
	{
		LinkedList object = new LinkedList();
		object.insert(10);
		object.insert(20);
		object.insert(30);
		object.display();
	
		while( !object.isEmpty() )
		{
			Node member = object.delete();
			System.out.print("Deleted ");
			member.displayNode();
			System.out.println("");
		}
		object.display();
	
		object.insert(40);
		object.insert(50);
		object.insert(60);
		object.display();

		System.out.println("Reversing the Linked List");
		object.reverse();

		object.display();

		Node objecttosearch = object.search(50);

		if( objecttosearch != null)
			System.out.println("Found Node : " + objecttosearch.item);
		else
			System.out.println("Cannot locate the node");

		Node objecttodelete = object.delete(50);

		if( objecttodelete != null )
			System.out.println("Deleted node : " + objecttodelete.item);
		else
			System.out.println("Cannot delete the node");


		object.display();
		
	} 
}

OUTPUT:

labuser@ubuntu:~/linkedlist$ java LinkedListBlog
List items from first to last :
[30]
[20]
[10]

Deleted [30]

Deleted [20]

Deleted [10]

List items from first to last :

List items from first to last :
[60]
[50]
[40]

Reversing the Linked List
List items from first to last :
[40]
[50]
[60]

Found Node : 50
Deleted node : 50
List items from first to last :
[40]
[60]

labuser@ubuntu:~/linkedlist$

About these ads

One response to “Algorithm to Reverse a Linked List

  1. sanstechbytes November 26, 2011 at 10:53 am

    The course notes are really good. :). By the way, if you’re preparing for a tech/coding interview, this is a great buy – Buy Cracking The Coding Interview: 150 Programming Questions And Solutions from Flipkart.com

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: