Search Your Topic

config
Tuesday, 11 July 2017 12:27

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

Written by
Rate this item
(0 votes)

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”

linkedlist

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<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);

 

}
Output:
Node no. 4 from last is 35

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

Read 71 times
Anish Sir

"I am delighted once again to pen the welcome note to the Tosh!Yas Technologies ."

 Call +91 74 88 34 7779  | Email : anishsingh@live.com

toshiyas.in

Leave a comment

Make sure you enter all the required information, indicated by an asterisk (*). HTML code is not allowed.