print single linked list in reverse order

This is frequently asked question as we would be having only forward reference but not the backward reference to traverse the single linked list (SLL) in backward direction.

We can do this in two different ways

  • Recursive Way: Using recursion we can traverse the list in backward direction because when we recursively traverse SLL in forward direction all the method calls are kept on the stack which will be revisited in the same order but in reverse direction till the base condition is met.
  • Linear programming by using stack implementation.

Recursive Way

	public void reverse(Node node) {
		if (node != null) {
			reverse(node.next);
			System.out.print("  " + node.value);
		}
	}

Linear Programming:

	public void reverse1(Node node) {
		Deque<Node> stack = new ArrayDeque<Node>();
		while (node != null) {
			stack.push(node);
			node = node.next;
		}
		// print the stack
		while (!stack.isEmpty())
			System.out.println(stack.poll().value);
	}

Full Source Code

package algorithms.lists;
import java.util.ArrayDeque;
import java.util.Deque;

public class SLLReverse {
	private static Node root, tmp;

	public void reverse(Node node) {
		if (node != null) {
			reverse(node.next);
			System.out.print("  " + node.value);
		}
	}

	public void reverse1(Node node) {
		Deque<Node> stack = new ArrayDeque<Node>();
		while (node != null) {
			stack.push(node);
			node = node.next;
		}
		// print the stack
		while (!stack.isEmpty())
			System.out.println(stack.poll().value);
	}

	public void insert(Node n) {
		if (root == null) {
			root = n;
			tmp = root;
		} else {
			tmp.next = n;
			tmp = n;
		}
	}

	public static void main(String[] str) {
		SLLReverse s = new SLLReverse();
		// build the SLL
		for (int i = 0; i < 10; i++) {
			s.insert(new Node(i));
		}

		// print SLL in reverse order
		s.reverse1(s.root);
	}

	static class Node {
		Node next;
		int value;

		Node(int i) {
			value = i;
		}
	}
}
Advertisements

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

Mawazo

Mostly technology with occasional sprinkling of other random thoughts

amintabar

Amir Amintabar's personal page

101 Books

Reading my way through Time Magazine's 100 Greatest Novels since 1923 (plus Ulysses)

Seek, Plunnge and more...

My words, my world...

ARRM Foundation

Do not wait for leaders; do it alone, person to person - Mother Teresa

Executive Management

An unexamined life is not worth living – Socrates

Diabolical or Smart

Nitwit, Blubber, Oddment, Tweak !!

javaproffesionals

A topnotch WordPress.com site

thehandwritinganalyst

Just another WordPress.com site

coding algorithms

"An approximate answer to the right problem is worth a good deal more than an exact answer to an approximate problem." -- John Tukey