algorithm to find nth last element of a single linked list

We can do this in two ways

  • Recursive Approach
  • Iterative Approach

Problem Statement: Lets say the Single Linked List (SLL) is 0-1-2-3-4-5-6-7-8-9, and we want to find last 3rd element (say ‘pos=3’) in this SLL

Recursive Approach:
Take a instance/global variable to track the post recursive call and when it is same as ‘pos’, print the value.
Order of complexity: O(n) for pre recursive calls and O(n) for post recursive calls, which is = O(2n)

	public void getElementRecursive(Node node, int pos) {
		if(node != null) {
			getElementRecursive(node.next, pos);
			ctr++;
			if(pos==ctr) {
				System.out.println("Middle element of the list is: " + node.value);
			}
		}
	}

Iterative Approach:
Take two pointers ‘n1’ and ‘n2’, as first step – move pointer n1 to ‘n-1’ positions and as second step – move n1 and n2 simultaneously till n1 is not equal to null.
Order of complexity: O(pos) for first step and O(n-pos) for second step, which is = O(n)

	public void getElementIterative(Node node, int pos) {

		Node n1 = node;
		Node n2 = node;

		for(int i=0; i<pos-1; i++) {
			n1 = n1.next;
		}

		while(n1 != null && n1.next != null) {
			n1 = n1.next;
			n2 = n2.next;
		}
		System.out.println("Middle element of the list is: " + n2.value);
	}

Note: Out of these two approaches, recursive first comes to mind, but looking at the complexities iterative approach is better to implement this algorithm.

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