Tuesday, 11 July 2017 12:32

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

Written by
Rate this item

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

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

`/* 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 (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 */`
`  ``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, 5);`
`  ``return` `0; `
`}`
`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);` `}` ime 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. `// 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);`   `}` `Output:` `Node no. 4 from last is 35` Time Complexity: O(n) where n is the length of linked list.