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
- We have to find an nth element from the last node of the list.
- Create two pointers, p1 and p2, that point to the beginning of the node.
- 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).
- 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.
- Repeat the step 4.
Program
[code lang=”c”]
#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
}
[/code]
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).