CareerCup

Standard trailing pointer trick.

just easy one by use of the trailing pointers technique use this code for this one:
struct node *Nthlast(struct node *L,int n)
{
int c=0;
struct node *temp=L,*temp2=L2;
if(!L)
return L;
while(c!=n-1 && temp1!=NULL)
{
c++;
temp1=temp1->next;
}
if(temp1==NULL)
return NULL:

while(temp1->next!=NULL)
{
temp2=temp2->next;
temp1=temp1->next;
}

return temp2;

}

two traversals to get it done!

1st, reverse the list to the new list
2nd, from the previous list's last one, we reverse this new list back to original order, at the same time we count the number of current handling node, when it's nth , we print it out.

ele findLastNth(node *head, int n)
{
int i;
node *p, *q ,*cur;
p=cur=head;
q=p->next;
p->next=NULL;
while(q!=NULL){
cur=q;
q=q->next;
cur->next=p;
p=cur;
}
q=p->next;
p->next=NULL;
i=1;
while(q!=NULL){
cur=q;
q=q->next;
cur->next=p;
if(i==n)
return p->ele;
p=cur;
i++;
}
}

one traverse should be enough by keeping a count how many first pointer is ahead of the second one.

we can just traverse to the end of the list and we will get the nth last element right? Why are you reversing it in the first place? not required i think.

1. check size of the LL

2. run two pointers
one i++
other J+=2
when j reaches N , i will be at Center
then we know that there is equal distance from N now increment to the asked[Kth last element]

Node *A, *B

A = head
B = head

for i in [0 to n-1]
if(!A) return -1
A=A->next

while (!A)
A=A->next
B=B->next

return B

Node* NthLast(Node *root,int n)
{
      int i=0;
      Node *nth,*last;
      last = root;
      while(i< n)
      {
              last = last->next;
              i++;
      }


      nth = root;
      while(last != NULL)
      {
              last = last-next;
              nth = nth->next;
      }
      return nth;

}

[1].By recursion.
[2].Take two pointers.First will point to first node and second will point to nth node from the first.we will move both pointers untill we get NULL at second pointer.thats all first pointer is pointing to you ANS(nth element from the last).

Ask if its a doubly linked list, if so just traverse to the anthem element backwards .

void findNthFromLast(struct Node* headNode, int n)
{
/*this has to be static so that it holds it's value from
call to call because of the fact that a non-static variable
will not hold it's value since the variable will just be local
to the function if it's not static and will not be preserved
across call stack: */

static int i = 0;
//base case when we reach the end of linked list:
if(headNode == NULL)
return;
//this is where head pointer is advanced (head->next)...
findNthFromLast(headNode->next, n);
//increment i and check to see if equals n
//if it does equal n then print out the element's data
if(++i == n)
printf("%d", headNode->elementData);
}