# Find the n’th Node from the end of a given Linked List

Objective: Given a linked list and integer ‘n’, write an algorithm to find the nth node from the end in the Linked List.

Example:

```Original List : ->1->2->8->3->7->0->4
Output : 3rd Element from the end is : 7
```

Input: An unsorted linked list and integer k

Output: The kth to Last Element of a Singly Linked List

Approach:

Recursive Approach:

• Recurse through the Linked list
• When we reach to the end of the list, base case will return 0
• Now with each passing back call through stack, add 1 and return.
• When count hits k, print the value.

Iterative Approach:

• Take two pointers approach
• Move first pointer by k
• now move both the pointers and when the first pointer reaches the end of the list the second pointer will be at the kth node from the end.
• Return the kth node data.

Complete Code:

 public class KthToLastElementofLL { public int kthByRecursion(Node head, int k){ if(head==null){ return 0; } int i = kthByRecursion(head.next, k)+1; if(i==k){ System.out.println(head.data); } return i; } public int kthByIteration(Node head, int k){ if(head==null){ return 0; } Node curr = head; while(k>0){ curr=curr.next; k—; } Node sec = head; while(curr!=null){ curr = curr.next; sec = sec.next; } int i = sec.data; return i; } public void display(Node head){ Node n=head; while(n!=null){ System.out.print("->t;" + n.data); n=n.next; } } public static void main(String args[]){ Node n = new Node(1); n.next = new Node(2); n.next.next = new Node(8); n.next.next.next = new Node(3); n.next.next.next.next = new Node(7); n.next.next.next.next.next = new Node(0); n.next.next.next.next.next.next = new Node(4); System.out.print("Original List : "); KthToLastElementofLL rm = new KthToLastElementofLL(); rm.display(n); System.out.print("\n Recursion::3rd Element from the end is : "); rm.kthByRecursion(n, 3); System.out.print("\n Iteration::5th Element from the end is : " + rm.kthByIteration(n, 5)); } } class Node{ int data; Node next; public Node(int data){ this.data = data; next = null; } }

Output:

```Original List : ->1->2->8->3->7->0->4
Recursion::3rd Element from the end is : 7
Iteration::5th Element from the end is : 8
```