# Program to Find Nth Node from the End of a Linked List

• Write a C program to print Nth node from end of linked list.
• Find Nth last node of linked list.

Given a singly linked list and an integer N(N <= length of linked list), we have to find the Nth node from end of linked list. Check following example :

```Input Linked List
2-->4-->9-->1-->7-->10-->11
5th node from end of linked list is : 9
```

## Find Nth last node using two node pointers

Algorithm to find Nth last node of linked list
1. First of all, find the length of linked list(let it be L). Given problem is valid only if L >= N else invalid problem. Invalid problem example : Find 10th last node of a linked list whole length is 6.
2. We will use two pointers "front" and "back" pointer. Initially, set both pointer to head node.
3. Move "front" pointer N-1 node ahead. This will create a difference of N-1 nodes between "front" and "back" pointer.
4. Now, move both pointer together one node at a time until "front" pointer reaches tail node.
5. When "front" pointer reaches last node, "back" pointer will point to Nth last node of linked list.
Time Complexity: O(N), where N is the length of given linked list.

In this program, we will use a user defined function "getNthLastNode" which takes head node pointer of a linked list and N as input parameters and return a pointer to Nth last node of linked list.

```struct node* getNthLastNode(struct node* head, int n){
struct node *front, *back;
int i;
/* N should be less than length of Linked List */
printf("Error : n is greater than length of Linked List\n");
return NULL;
}
/* Move front pointer n-1 nodes. This will create
a difference of n-1 nodes between front and back */
for(i = 0; i < n-1; i++){
front = front->next;
}
/* Now, move both pointers together till front reaches
last node of linked list. when front reaches last node
back pointer will be pointing to Nth last node*/
while(front->next != NULL){
front = front->next;
back = back->next;
}

return back;
}
```

C program to find Nth last node using two pointers
```#include <stdio.h>
#include <stdlib.h>

/* A structure of linked list node */
struct node {
int data;
struct node *next;

void initialize(){
}

/*
Given a Inserts a node in front of a singly linked list.
*/
void insert(int num) {
/* Create a new Linked List node */
struct node* newNode = (struct node*) malloc(sizeof(struct node));
newNode->data  = num;
/* Next pointer of new node will point to head node of linked list  */
printf("Inserted Element : %d\n", num);
}

/* Input Validation */
printf("Error : Invalid node pointer !!!\n");
return;
}2

int length =0;
length++;
}
return length;
}

struct node* getNthLastNode(struct node* head, int n){
struct node *front, *back;
int i;
/* N should be less than length of Linked List */
printf("Error : n is greater than length of Linked List\n");
return NULL;
}
/* Move front pointer n-1 nodes. This will create
a difference of n-1 nodes between front and back */
for(i = 0; i < n-1; i++){
front = front->next;
}
/* Now, move both pointers together till front reaches
last node of linked list. when front reaches last node
back pointer will be pointing to Nth last node*/
while(front->next != NULL){
front = front->next;
back = back->next;
}

return back;
}
/*
*/
while (nodePtr != NULL) {
printf("%d", nodePtr->data);
nodePtr = nodePtr->next;
if(nodePtr != NULL)
printf("-->");
}
}

int main() {
int N;
struct node *NthNode;
initialize();
insert(3);
insert(8);
insert(12);
insert(0);
insert(35);
insert(6);

printf("\nEnter value of N\n");
scanf("%d", &N);
printf("Nth Last node is %d", NthNode->data);
return 0;
}
```
Output
```Inserted Element : 3
Inserted Element : 8
Inserted Element : 12
Inserted Element : 0
Inserted Element : 35
Inserted Element : 6

6-->35-->0-->12-->8-->3
Enter value of N
3
Nth Last node is 12
```

Alternate Method

## Find Nth node from end of Linked List by counting nodes

Algorithm to find Nth last node of linked list