## algorithm to find nth last element of a single linked list

May 21, 2013 Leave a comment

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.

## Recent Comments