- Write a C program to print N
^{th}node from end of linked list. - Find N
^{th}last node of linked list.

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

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

## Find N^{th} last node using two node pointers

**Algorithm to find N**

^{th}last node of linked listLet "head" be the head pointer of given linked list.

- 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 10
^{th}last node of a linked list whole length is 6. - We will use two pointers "front" and "back" pointer. Initially, set both pointer to head node.
- Move "front" pointer N-1 node ahead. This will create a difference of N-1 nodes between "front" and "back" pointer.
- Now, move both pointer together one node at a time until "front" pointer reaches tail node.
- When "front" pointer reaches last node, "back" pointer will point to N
^{th}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 N^{th} last node of linked list.

struct node* getNthLastNode(struct node* head, int n){ struct node *front, *back; int i; front = back = head; /* N should be less than length of Linked List */ if(n > getLength(head)){ 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; } *head; void initialize(){ head = NULL; } /* 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 */ newNode->next = head; /* make new node as new head of linked list */ head = newNode; printf("Inserted Element : %d\n", num); } int getLength(struct node *head){ /* Input Validation */ if (head == NULL) { printf("Error : Invalid node pointer !!!\n"); return; }2 int length =0; while(head != NULL){ head = head->next; length++; } return length; } struct node* getNthLastNode(struct node* head, int n){ struct node *front, *back; int i; front = back = head; /* N should be less than length of Linked List */ if(n > getLength(head)){ 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; } /* Prints a linked list from head node till tail node */ void printLinkedList(struct node *nodePtr) { while (nodePtr != NULL) { printf("%d", nodePtr->data); nodePtr = nodePtr->next; if(nodePtr != NULL) printf("-->"); } } int main() { int N; struct node *NthNode; initialize(); /* Creating a linked List*/ insert(3); insert(8); insert(12); insert(0); insert(35); insert(6); printf("\nLinked List\n"); printLinkedList(head); printf("\nEnter value of N\n"); scanf("%d", &N); NthNode = getNthLastNode(head, 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 Linked List 6-->35-->0-->12-->8-->3 Enter value of N 3 Nth Last node is 12

**Alternate Method**

## Find N^{th} node from end of Linked List by counting nodes

**Algorithm to find N**

^{th}last node of linked listLet "head" be the head pointer of given linked list.

- First of all, find the length of linked list(let it be L). Given problem is valid only if L >= N else invalid problem.
- N
^{th}node from end is equal to (L - N + 1)^{th}node from the beginning of the Linked List. - Using a loop, traverse the linked list by maintaining a counter. Return (L - N + 1)
^{th}node from front of linked list.

**Time Complexity**: O(N), where N is the length of given linked list.