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

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 n = 3, 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.

## C

 `// Simple C program to find n'th node from end ` `#include ` `#include ` ` `  `/* 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``; ` ` `  `    ``temp = head; ` ` `  `    ``// 2) get the (len-n+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 */` `new_node->next = (*head_ref); ` ` `  `/* move the head to point to the new node */` `(*head_ref) = 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 ` `push(&head, 20); ` `push(&head, 4); ` `push(&head, 15); ` `push(&head, 35); ` ` `  `printNthFromLast(head, 4); ` `return` `0;  ` `} `

## Java

 `// Simple Java program to find n'th node from end of linked list ` `class` `LinkedList ` `{ ` `    ``Node head; ``// head of the list ` ` `  `    ``/* Linked List node */` `    ``class` `Node ` `    ``{ ` `        ``int` `data; ` `        ``Node next; ` `        ``Node(``int` `d) ` `        ``{ ` `            ``data = d; ` `            ``next = ``null``; ` `        ``} ` `    ``} ` ` `  `    ``/* Function to get the nth node from the last of a ` `       ``linked list */` `    ``void` `printNthFromLast(``int` `n) ` `    ``{ ` `        ``int` `len = ``0``; ` `        ``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``; ` ` `  `        ``temp = head; ` ` `  `        ``// 2) get the (len-n+1)th node from the begining ` `        ``for` `(``int` `i = ``1``; i < len-n+``1``; i++) ` `            ``temp = temp.next; ` ` `  `        ``System.out.println(temp.data); ` `    ``} ` ` `  `    ``/* Inserts a new Node at front of the list. */` `    ``public` `void` `push(``int` `new_data) ` `    ``{ ` `        ``/* 1 & 2: Allocate the Node & ` `                  ``Put in the data*/` `        ``Node new_node = ``new` `Node(new_data); ` ` `  `        ``/* 3. Make next of new Node as head */` `        ``new_node.next = head; ` ` `  `        ``/* 4. Move the head to point to new Node */` `        ``head = new_node; ` `    ``} ` ` `  `    ``/*Drier program to test above methods */` `    ``public` `static` `void` `main(String [] args) ` `    ``{ ` `        ``LinkedList llist = ``new` `LinkedList(); ` `        ``llist.push(``20``); ` `        ``llist.push(``4``); ` `        ``llist.push(``15``); ` `        ``llist.push(``35``); ` ` `  `        ``llist.printNthFromLast(``4``); ` `    ``} ` `}``// This code is contributed by Rajat Mishra `

## Python3

 `# Simple Python3 program to find ` `# n'th node from end ` `class` `Node: ` `    ``def` `__init__(``self``, new_data): ` `        ``self``.data ``=` `new_data ` `        ``self``.``next` `=` `None` `     `  `class` `LinkedList: ` `    ``def` `__init__(``self``): ` `        ``self``.head ``=` `None` ` `  `    ``# createNode and and make linked list ` `    ``def` `push(``self``, new_data): ` `        ``new_node ``=` `Node(new_data) ` `        ``new_node.``next` `=` `self``.head ` `        ``self``.head ``=` `new_node ` ` `  `    ``# Function to get the nth node from  ` `    ``# the last of a linked list  ` `    ``def` `printNthFromLast(``self``, n): ` `        ``temp ``=` `self``.head ``# used temp variable ` `         `  `        ``length ``=` `0` `        ``while` `temp ``is` `not` `None``: ` `            ``temp ``=` `temp.``next` `            ``length ``+``=` `1` `         `  `        ``# print count  ` `        ``if` `n > length: ``# if entered location is greater  ` `                       ``# than length of linked list ` `            ``print``(``'Location is greater than the'` `+` `                         ``' length of LinkedList'``) ` `            ``return` `        ``temp ``=` `self``.head ` `        ``for` `i ``in` `range``(``0``, length ``-` `n): ` `            ``temp ``=` `temp.``next` `        ``print``(temp.data) ` ` `  `# Driver Code         ` `llist ``=` `LinkedList()  ` `llist.push(``20``)  ` `llist.push(``4``)  ` `llist.push(``15``)  ` `llist.push(``35``) ` `llist.printNthFromLast(``4``) ` ` `  `# This code is contributed by Yogesh Joshi `

Output:

` 35 `

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

 `void` `printNthFromLast(``struct` `Node* head, ``int` `n)  ` `{ ` `    ``static` `int` `i = 0;  ` `    ``if` `(head == NULL) ` `       ``return``; ` `    ``printNthFromLast(head->next, n); ` `    ``if` `(++i == n) ` `       ``printf``(``"%d"``, head->data); ` `} `

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.

Implementation:

## C

 `// C program to find n'th node from end using slow and ` `// fast pointers ` `#include ` `#include ` ` `  `/* 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) ` `{ ` `  ``struct` `Node *main_ptr = head; ` `  ``struct` `Node *ref_ptr = head; ` ` `  `  ``int` `count = 0; ` `  ``if``(head != NULL) ` `  ``{ ` `     ``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 */` `  ``new_node->next = (*head_ref);     ` ` `  `  ``/* move the head to point to the new node */` `  ``(*head_ref)    = new_node; ` `} ` ` `  `/* Drier program to test above function*/` `int` `main() ` `{ ` `  ``/* Start with the empty list */` `  ``struct` `Node* head = NULL; ` `  ``push(&head, 20); ` `  ``push(&head, 4); ` `  ``push(&head, 15); ` `  ``push(&head, 35); ` ` `  `  ``printNthFromLast(head, 4); ` `} `

## Java

 `// Java program to find n'th node from end using slow and ` `// fast pointers ` `class` `LinkedList ` `{ ` `    ``Node head; ``// head of the list ` ` `  `    ``/* Linked List node */` `    ``class` `Node ` `    ``{ ` `        ``int` `data; ` `        ``Node next; ` `        ``Node(``int` `d) ` `        ``{ ` `            ``data = d; ` `            ``next = ``null``; ` `        ``} ` `    ``} ` ` `  `    ``/* Function to get the nth node from end of list */` `    ``void` `printNthFromLast(``int` `n) ` `    ``{ ` `        ``Node main_ptr = head; ` `        ``Node ref_ptr = head; ` ` `  `        ``int` `count = ``0``; ` `        ``if` `(head != ``null``) ` `        ``{ ` `            ``while` `(count < n) ` `            ``{ ` `                ``if` `(ref_ptr == ``null``) ` `                ``{ ` `                    ``System.out.println(n+``" is greater than the no "``+ ` `                                      ``" of nodes in the list"``); ` `                    ``return``; ` `                ``} ` `                ``ref_ptr = ref_ptr.next; ` `                ``count++; ` `            ``} ` `            ``while` `(ref_ptr != ``null``) ` `            ``{ ` `                ``main_ptr = main_ptr.next; ` `                ``ref_ptr = ref_ptr.next; ` `            ``} ` `            ``System.out.println(``"Node no. "``+n+``" from last is "``+ ` `                               ``main_ptr.data); ` `        ``} ` `    ``} ` ` `  `    ``/* Inserts a new Node at front of the list. */` `    ``public` `void` `push(``int` `new_data) ` `    ``{ ` `        ``/* 1 & 2: Allocate the Node & ` `                  ``Put in the data*/` `        ``Node new_node = ``new` `Node(new_data); ` ` `  `        ``/* 3. Make next of new Node as head */` `        ``new_node.next = head; ` ` `  `        ``/* 4. Move the head to point to new Node */` `        ``head = new_node; ` `    ``} ` ` `  `    ``/*Drier program to test above methods */` `    ``public` `static` `void` `main(String [] args) ` `    ``{ ` `        ``LinkedList llist = ``new` `LinkedList(); ` `        ``llist.push(``20``); ` `        ``llist.push(``4``); ` `        ``llist.push(``15``); ` `        ``llist.push(``35``); ` ` `  `        ``llist.printNthFromLast(``4``); ` `    ``} ` `} ``// This code is contributed by Rajat Mishra `

## Python

 `# Python program to find n'th node from end using slow ` `# and fast pointer ` ` `  `# Node class  ` `class` `Node: ` ` `  `    ``# Constructor to initialize the node object ` `    ``def` `__init__(``self``, data): ` `        ``self``.data ``=` `data ` `        ``self``.``next` `=` `None` ` `  `class` `LinkedList: ` ` `  `    ``# Function to initialize head ` `    ``def` `__init__(``self``): ` `        ``self``.head ``=` `None` ` `  `    ``# Function to insert a new node at the beginning ` `    ``def` `push(``self``, new_data): ` `        ``new_node ``=` `Node(new_data) ` `        ``new_node.``next` `=` `self``.head ` `        ``self``.head ``=` `new_node ` ` `  `    ``def` `printNthFromLast(``self``, n): ` `        ``main_ptr ``=` `self``.head ` `        ``ref_ptr ``=` `self``.head  ` `     `  `        ``count  ``=` `0`  `        ``if``(``self``.head ``is` `not` `None``): ` `            ``while``(count < n ): ` `                ``if``(ref_ptr ``is` `None``): ` `                    ``print` `"%d is greater than the no. pf nodes in list"` `%``(n) ` `                    ``return` `  `  `                ``ref_ptr ``=` `ref_ptr.``next` `                ``count ``+``=` `1` ` `  `        ``while``(ref_ptr ``is` `not` `None``): ` `            ``main_ptr ``=` `main_ptr.``next`  `            ``ref_ptr ``=` `ref_ptr.``next` ` `  `        ``print` `"Node no. %d from last is %d "` `%``(n, main_ptr.data) ` ` `  ` `  `# Driver program to test above function ` `llist ``=` `LinkedList() ` `llist.push(``20``) ` `llist.push(``4``) ` `llist.push(``15``) ` `llist.push(``35``) ` ` `  `llist.printNthFromLast(``4``) ` ` `  `# This code is contributed by Nikhil Kumar Singh(nickzuck_007) `

Output:

`Node no. 4 from last is 35`

Time Complexity: O(n) where n is the length of linked list.

Please write comments if you find the above codes/algorithms incorrect, or find other ways to solve the same problem.