# 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  C Programming - Backtracking | Set 6 (Hamiltonian Cycle)

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 