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

C++ Program to create a Program for n’th node from the end of a Linked List or nth node end linked list.

To nicely understand this example to the nth node end linked list, you should have the knowledge of following C++ programming topics:

Method 1 (Use length of the linked list)

Calculate the length of Linked List. Let the length be len.
Print the (len – n + 1)th node from the beginning of the Linked List.

Program to find n’th node from the 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

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 the linked list.

NEXT UP IN Link List

Ask your questions and clarify your/others doubts on Program to nth node end linked list by commenting. Documentation