{"id":27029,"date":"2018-01-02T20:59:35","date_gmt":"2018-01-02T15:29:35","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=27029"},"modified":"2018-01-02T20:59:35","modified_gmt":"2018-01-02T15:29:35","slug":"c-algorithm-find-nth-node-end-linked-list","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/c-algorithm-find-nth-node-end-linked-list\/","title":{"rendered":"C Algorithm – Find n\u2019th node from the end of a Linked List"},"content":{"rendered":"

Given a Linked List and a number n, write a function that returns the value at the n\u2019th node from end of the Linked List.<\/p>\n

Method 1 (Use length of linked list)<\/strong>
\n1) Calculate the length of Linked List. Let the length be len.
\n2) Print the (len \u2013 n + 1)th node from the begining of the Linked List.<\/p>\n

C Programming:<\/strong><\/p>\n

<\/div> 
\/\/ 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; }<\/code><\/pre> <\/div>\n
Output:<\/strong><\/p>\n
35<\/pre>\n
Following is a recursive C code for the same method. Thanks to Anuj Bansal for providing following code.<\/p>\n[ad type=”banner”]\n
C Programming:<\/strong><\/p>\n
 
 <\/div> 
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);}<\/code><\/pre> <\/div>\n
Time Complexity:<\/strong> O(n) where n is the length of linked list.
\nMethod 2 (Use two pointers) <\/strong>
\nMaintain two pointers \u2013 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.<\/p>\n
C Programming:<\/strong><\/p>\n
 
 <\/div> 
\/\/ C program to find n'th node from end using slow and\/\/ fast pointers#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){  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);}<\/code><\/pre> <\/div>\n
Output:<\/strong><\/p>\n
Node no. 4 from last is 35<\/pre>\n
Time Complexity:<\/strong> O(n) where n is the length of linked list<\/p>\n[ad type=”banner”]\n","protected":false},"excerpt":{"rendered":"
C Algorithm – Find n\u2019th 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<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[69866,1,79476,79478],"tags":[80492,80659,80489,80493,80666,80660,80491],"class_list":["post-27029","post","type-post","status-publish","format-standard","hentry","category-c-programming","category-coding","category-linked-list","category-singly-linked-list","tag-find-middle-element-in-linked-list-java","tag-find-nth-element-in-linked-list","tag-find-nth-element-in-linked-list-c","tag-find-nth-to-last-element-in-a-linked-list-recursion","tag-linked-list-in-cc-delete-a-node-at-nth-position","tag-remove-nth-node-from-end-of-list-c","tag-search-a-node-in-linked-list-in-c"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27029","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=27029"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27029\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=27029"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=27029"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=27029"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}