# C Algorithm – Find n’th node from the end of a Linked List

C Algorithm - Find n’th node from the end of a Linked List - Linked List - Given a Linked List and a number n, write a function that returns the value

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.

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.

C Programming:

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

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;

// 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()
{

return 0;
}``````

Output:

`35`

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

C Programming:

``````void printNthFromLast(struct node* head, int n)
{
static int i = 0;
return;
if (++i == n)
}``````

Time Complexity: O(n) where n is the length of linked list.
Method 2 (Use two pointers)
Maintain two pointers – reference pointer and main pointer. Initialize both reference and main pointers to head. First move reference pointer to n nodes from head. Now move both pointers one by one until reference pointer reaches end. Now main pointer will point to nth node from the end. Return main pointer.

READ  Python programming - Sieve of Eratosthenes

C Programming:

``````// C program to find n'th node from end using slow and
// fast pointers
#include<stdio.h>
#include<stdlib.h>

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 count = 0;
{
while( count < n )
{
if(ref_ptr == NULL)
{
printf("%d is greater than the no. of "
"nodes in list", n);
return;
}
ref_ptr = ref_ptr->next;
count++;
} /* End of while*/

while(ref_ptr != NULL)
{
main_ptr = main_ptr->next;
ref_ptr  = ref_ptr->next;
}
printf("Node no. %d from last is %d ",
n, main_ptr->data);
}
}

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()
{

}``````

Output:

`Node no. 4 from last is 35`

Time Complexity: O(n) where n is the length of linked list #### Venkatesan Prabu

Wikitechy Founder, Author, International Speaker, and Job Consultant. My role as the CEO of Wikitechy, I help businesses build their next generation digital platforms and help with their product innovation and growth strategy. I'm a frequent speaker at tech conferences and events.