Reversing a singly linked list in java

Another classic interview question…

Reverse a singly list so that
a -> b -> c -> d -> e becomes: e -> d -> b -> c -> a

A very theoretical exercise by the way since the java api contains a method to reverse a list in the java.util package , Collections.reverse (list)…

The reversal is implemented below both:

– procedurally, using an algorithm which (I believe) was originally published in ‘Fundamentals of Data Structures’ by Horowitz and Sahni.

– recursively – my own design ^-^


public class ReverseList {

	public static void main (String args[]){

		//build a singly linked list

		//a -> b -> c -> d -> e

		Node a = new Node ("a");

		Node b = new Node ("b");

		Node c = new Node ("c");

		Node d = new Node ("d");

		Node e = new Node ("e");

		a.next = b;

		b.next = c;

		c.next = d;

		d.next = e;

		SinglyLinkedList list = new SinglyLinkedList();

		list.head  = a;

		System.out.println ("Original list");

		list.print(list.head);

		list.reverse ();

		System.out.println ("\n\nList reversed with procedural method");

		list.print(list.head);

		list.reverse (null, list.head);

		System.out.println ("\n\nList re-reversed with recursive method");

		list.print(list.head);

	}

}

class SinglyLinkedList {

	Node     head;

	public void print(Node node){

		System.out.print (node);

		if (node.next!=null){

			System.out.print (" -> ");

			print(node.next);

		}

	}

	//procedural reverse

	public void   reverse() {

		Node n3 = head;

		Node n2 = null;

		Node n1 = null;

		while (n3!= null) {

			n1 = n2;

			n2 = n3;

			n3 = n2.next;

			n2.next = n1;

		}

		head = n2;

	}

	//recursive reverse

	public void reverse (Node n1, Node n2){

		Node n3 = n2.next;

		n2.next = n1;

		if (n3!=null){

			reverse (n2, n3);

		}else {

			head = n2;

		}

	}

}

class Node {

	Node   next;

	String value;

	Node (String value ) {

		this.value = value;

	}

	public String toString () {

		return value;

	}

}

Advertisements

3 thoughts on “Reversing a singly linked list in java

  1. Pingback: Linked List Reverse | dheeraj9823

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