Devise an efficient algorithm for finding the Nth element from last in a linked list.
Eg. List [1, 2, 3, 4, 5, 6, 7, 8]
6th element from last = 3
Click here to see the solution.
p.s. - For Remarks please hit the given link once. For Hint, hit it twice and for the solution, hit it thrice.
Courtesy: Vibhaj
Hints: No hints. Hit again for solution |
|
Solution:
We use two pointers. The first pointer alone is moved N elements.
Then both pointers are moved until first one reaches the end.
Now the second pointer points to the Nth element from last.
Complexity:
1. Time : O(N)
2. Space : O(1)
Code:
void nth_last(int *list, int N, int *result){
int *tmp = list, i=N;
*result = list;
while(N--)
tmp = tmp->next;
while(tmp = tmp->next)
result = result->next;
}
|
|
|
Posts
#include
#include
#include
struct node {
int data;
struct node *next;
};
void find_node(struct node **);
int main()
{
struct node *temp,*first, *last;
int i;
first=NULL;
int num;
int n;
printf ("enter the number of element \n");
scanf ("%d",&n);
printf ("enter the numbers \n");
for (i=0;idata=num;
temp->next=NULL;
first=temp;
}
else {
temp->data=num;
temp->next=NULL;
last->next=temp;
}
last=temp;
}
find_node(&first);
getch();
return 0;
}
void find_node(struct node **q)
{
int i;
struct node *t;
t=*q;
int n;
int j;
j=0;
printf ("enter the position \n");
scanf ("%d",&n);
while (t!=NULL){
j++;
t=t->next;
}
int k;
k=j-n;
struct node *r;
r=*q;
for (i=0;inext;
}
printf ("the node is\n");
printf ("%d\n",r->data);
}