To find nth to last element of a Singly LinkedList

To find nth to last element of a Singly LinkedList

Question

Write a program to create a Singly LinkedList and find nth to the last element. Get the input from the user.

 

Logic

  1. We have to find an nth element from the last node of the list.
  2. Create two pointers, p1 and p2, that point to the beginning of the node.
  3. Increment p2 by n- 1 position, to make it point to the nth node from the beginning ( to make the distance of between p1 and p2).
  4. Check for p2->next == null if yes return value of p1, otherwise increment p1 and p2. If next of p2 is null it means p1 points to the nth node from the last as the distance between the two is n.
  5. Repeat the step 4.

Program

#include<stdio.h>
#include<stdlib.h>
/*Creating structure*/
 struct node
{
    int data;
    struct node* next;                  //link to next node in list
};
/*Creating new node*/
 struct node* create(int data)
 {
     struct node* temp = NULL;
     temp = (struct node*)malloc(sizeof(struct node)); //intializing pointer
     temp->data = data;
     temp->next = NULL;
     return temp;                       //passing the node address
 }
 struct node* nthToLast(struct node* head, int n)
 {
     if(head == NULL || n<1)            //if size of n lesser than one
        return NULL;

      struct node* p1 = (struct node*)malloc(sizeof(struct node));
      struct node* p2 = (struct node*)malloc(sizeof(struct node));

      /*Intializing the two node p1, p2 with head node*/
      p1 = head;
      p2 = head;

      /*Increment pointer p2 n steps ahead*/
     for(int i=0; i<n-1; i++)
     {
         if(p2 == NULL)                 //If the list ended, size of n is larger than list
             return NULL;

         p2 = p2->next;                 //Increment node
     }

     while(p2->next != NULL)            //incrementing both nodes till p2 reaches the end
     {
         p2 = p2->next;
         p1 = p1->next;
     }

     return p1;                         //n'th node from last
 }

 int main()
 {
     int n;
     struct node* node = (struct node*)malloc(sizeof(struct node));
     /*Creating linkedlist with values values 1,2,3,4,5*/
     node = create(1);
     node->next = create(2);
     node->next->next = create(3);
     node->next->next->next = create(4);
     node->next->next->next->next = create(5);
     printf("enter n :");
     scanf("%d",&n);

     struct node* N = (struct node*)malloc(sizeof(struct node));
     N = nthToLast(node,n);
     printf("%d",N->data);                  //printing the data of n'th node from end

 }

ANALYSIS

Time complexity: O(n) here n is the size of the list.

Space complexity: O(1)  here we are creating only 5 nodes for linkedlist so the size is constant. If we get ‘n’ from the user and create n nodes then complexity is O(n).

You might also like…

Medium Sum Set problem | Hackerearth

Follow For Instant Updates

Join WhatsApp Group: link
Join our Telegram Channel: link
Like our Facebook Page:  link
Subscribe to our Youtube channel: link

Sree Hari Sanjeev

The founder of Wisdom Overflow. Software Developer at Zoho Corporation.
0 0 votes
Article Rating
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments
0
Would love your thoughts, please comment.x
()
x