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:


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

__________________________________________________
Top Companies Interview Questions..-

Google Microsoft Amazon Facebook more..

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.
__________________________________________________

  • shivani kohli

    while(curr!=null){
    curr = curr.next;
    sec = sec.next;
    }

    What is this loop doing?

%d bloggers like this: