Program to Find Nth Node from the End of a Linked List

  • Write a C program to print Nth node from end of linked list.
  • Find Nth last node of linked list.

Given a singly linked list and an integer N(N <= length of linked list), we have to find the Nth node from end of linked list. Check following example : 

Input Linked List
2-->4-->9-->1-->7-->10-->11
5th node from end of linked list is : 9

Find Nth last node using two node pointers

Algorithm to find Nth last node of linked list
Let "head" be the head pointer of given linked list.
  1. First of all, find the length of linked list(let it be L). Given problem is valid only if L >= N else invalid problem. Invalid problem example : Find 10th last node of a linked list whole length is 6.
  2. We will use two pointers "front" and "back" pointer. Initially, set both pointer to head node.
  3. Move "front" pointer N-1 node ahead. This will create a difference of N-1 nodes between "front" and "back" pointer.
  4. Now, move both pointer together one node at a time until "front" pointer reaches tail node.
  5. When "front" pointer reaches last node, "back" pointer will point to Nth last node of linked list.
Time Complexity: O(N), where N is the length of given linked list.

In this program, we will use a user defined function "getNthLastNode" which takes head node pointer of a linked list and N as input parameters and return a pointer to Nth last node of linked list. 

struct node* getNthLastNode(struct node* head, int n){
    struct node *front, *back;
    int i;
    front = back = head;
    /* N should be less than length of Linked List */
    if(n > getLength(head)){
        printf("Error : n is greater than length of Linked List\n");
        return NULL;
    }
    /* Move front pointer n-1 nodes. This will create 
    a difference of n-1 nodes between front and back */
    for(i = 0; i < n-1; i++){
        front = front->next;
    }
    /* Now, move both pointers together till front reaches 
    last node of linked list. when front reaches last node 
    back pointer will be pointing to Nth last node*/
    while(front->next != NULL){
        front = front->next;
        back = back->next;
    }
    
    return back;
}
C program to find Nth last node using two pointers 
#include <stdio.h>
#include <stdlib.h>
 
/* A structure of linked list node */
struct node {
  int data;
  struct node *next;
} *head;

void initialize(){
    head = NULL;
}

/* 
Given a Inserts a node in front of a singly linked list. 
*/
void insert(int num) {
    /* Create a new Linked List node */
    struct node* newNode = (struct node*) malloc(sizeof(struct node));
    newNode->data  = num;
    /* Next pointer of new node will point to head node of linked list  */
    newNode->next = head;
    /* make new node as new head of linked list */
    head = newNode;
    printf("Inserted Element : %d\n", num);
}

int getLength(struct node *head){
    /* Input Validation */
    if (head == NULL) { 
       printf("Error : Invalid node pointer !!!\n");       
       return;  
    }2
     
    int length =0;
    while(head != NULL){
        head = head->next;
        length++;
    }
    return length;
}

struct node* getNthLastNode(struct node* head, int n){
    struct node *front, *back;
    int i;
    front = back = head;
    /* N should be less than length of Linked List */
    if(n > getLength(head)){
        printf("Error : n is greater than length of Linked List\n");
        return NULL;
    }
    /* Move front pointer n-1 nodes. This will create 
    a difference of n-1 nodes between front and back */
    for(i = 0; i < n-1; i++){
        front = front->next;
    }
    /* Now, move both pointers together till front reaches 
    last node of linked list. when front reaches last node 
    back pointer will be pointing to Nth last node*/
    while(front->next != NULL){
        front = front->next;
        back = back->next;
    }
    
    return back;
}
/*
Prints a linked list from head node till tail node 
*/
void printLinkedList(struct node *nodePtr) {
  while (nodePtr != NULL) {
     printf("%d", nodePtr->data);
     nodePtr = nodePtr->next;
     if(nodePtr != NULL)
         printf("-->");
  }
}
 
int main() {
    int N;
    struct node *NthNode;
    initialize();
    /* Creating a linked List*/
    insert(3);  
    insert(8); 
    insert(12); 
    insert(0);
    insert(35);
    insert(6);
    
    printf("\nLinked List\n");
    printLinkedList(head);
    printf("\nEnter value of N\n");
    scanf("%d", &N);
    NthNode = getNthLastNode(head, N);
    printf("Nth Last node is %d", NthNode->data);
    return 0;
}
Output
Inserted Element : 3
Inserted Element : 8
Inserted Element : 12
Inserted Element : 0
Inserted Element : 35
Inserted Element : 6

Linked List
6-->35-->0-->12-->8-->3
Enter value of N
3
Nth Last node is 12
Alternate Method

Find Nth node from end of Linked List by counting nodes

Algorithm to find Nth last node of linked list
Let "head" be the head pointer of given linked list.
  1. First of all, find the length of linked list(let it be L). Given problem is valid only if L >= N else invalid problem.
  2. Nth node from end is equal to (L - N + 1)thnode from the beginning of the Linked List.
  3. Using a loop, traverse the linked list by maintaining a counter. Return (L - N + 1)thnode from front of linked list.
Time Complexity: O(N), where N is the length of given linked list.
Posted by
Labels: