Part 8 of 26 in Linked List - set 02  

Get n'th node from the end of a linked list by admin

Problem statement

Given a singly linked list of integers and a number n, write a program to return nth node from the end of the linked list.

Input

Your method will have two parameters - pointer to the head of the linked list, and a number n. n will be at least 0 and less than the number of elements in the list.

Output

Your method must return the integer at nth node from end of the linked list.

Here we have to find and return the data at the node at a specific position from the tail.

  • Firstly we will calculate the length of our Linked List.
  • Now we have already been given N (position from tail).
  • If it is Nth from tail then it should be (length - N)th from head.
  • So we will simply traverse these much positions from the head and directly return the data at that position.

editorial written by ishabh

/*
  Get Nth element from the end in a linked list of integers
  Number of elements in the list will always be greater than N.
  Node is defined as
  struct Node
  {
     int data;
     struct Node *next;
  }
*/
int GetNthElementFromEnd(Node *head,int N)
{
    // Variable To store length of linked List
    int len = 0;

    // Pointer to store intermediate address of node
    // To be used in Traversing
    Node *traverse = head;

    // Calculating Length of the linked list
    // Moving Forward till we reach End
    while(traverse) {

        // Moving Forward
        traverse = traverse -> next;
        len++;
    }

    // These much positions from starting
    N = len - N;

    int DistFromHead = 1;
    traverse = head;

    // Traversing new N positions from head
    while(traverse) {
        // Returning Data of Nth position
        if(N == DistFromHead) return traverse->data; 

        // Moving in Forward Direction
        traverse = traverse -> next;
        DistFromHead++;
    }
}

featured solution by ishabh



To try out your code



Sign in

Sign up