Tuesday, 11 July 2017 12:27

Program for n’th node from the end of a Linked List

Written by
Rate this item

Given a Linked List and a number n, write a function that returns the value at the n’th node from end of the Linked List.

For example, if input is below list and 3 = 2, then output is “B” Method 1 (Use length of linked list)
1) Calculate the length of Linked List. Let the length be len.
2) Print the (len – n + 1)th node from the begining of the Linked List.

// Simple C program to find n'th node from end
#include<stdio.h>
#include<stdlib.h>

/* Link list node */
struct Node
{
int data;
struct Node* next;
};

/* Function to get the nth node from the last of a linked list*/
void printNthFromLast(struct Node* head, int n)
{
int len = 0, i;
struct Node *temp = head;

// 1) count the number of nodes in Linked List
while (temp != NULL)
{
temp = temp->next;
len++;
}

// check if value of n is not more than length of the linked list
if (len < n)
return;

// 2) get the (n-len+1)th node from the begining
for (i = 1; i < len-n+1; i++)
temp = temp->next;

printf ("%d", temp->data);

return;
}

void push(struct Node** head_ref, int new_data)
{
/* allocate node */
struct Node* new_node =
(struct Node*) malloc(sizeof(struct Node));

/* put in the data  */
new_node->data  = new_data;

/* link the old list off the new node */

/* move the head to point to the new node */
}

/* Drier program to test above function*/
int main()
{
/* Start with the empty list */
struct Node* head = NULL;

// create linked 35->15->4->20

return 0;
}
Output:
35

Following is a recursive C code for the same method. Thanks to Anuj Bansal for providing following code. 