Nth 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 nth node from end of the Linked List.

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 beginning of the Linked List.

#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);   getchar();   return 0; }

Following is a recursive C code for the same method.

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) 

Here is a solution which is often called as the solution that uses frames.

Suppose one needs to get to the 6th node from the end in this LL. First, just keep on incrementing the first pointer (ptr1) till the number of increments cross n (which is 6 in this case)


STEP 1 : 1(ptr1,ptr2) -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10

STEP 2 : 1(ptr2) -> 2 -> 3 -> 4 -> 5 -> 6(ptr1) -> 7 -> 8 -> 9 -> 10



Now, start the second pointer (ptr2) and keep on incrementing it till the first pointer (ptr1) reaches the end of the LL.


STEP 3 : 1 -> 2 -> 3 -> 4(ptr2) -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 (ptr1)


So here you have!, the nth node from the end pointed to by ptr2!

 
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:

#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);   printNthFromLast(head, 3);   getchar(); }

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

NOTE:

Write comments if you find the above codes/algorithms incorrect, or you have better solution to solve the above problem.