CareerCup

Use two pointers with the distance of 5 elements. Once the first pointer hit the end then we can either get the 5th elements or null if the list has less than 5 elements.

Node* fifthElementFromTheEnd(Node* head) {
  const int FIVE = 5;
  const int FOUR = 4;
  static Node* trailer[FIVE];
  int i;
  
  for(i=1;i<FIVE;i++) trailer[i] = NULL;
  for(trailer[i=0] = NULL;trailer[i]->next;++i%=FIVE) 
   trailer[(i+1)%FIVE] = trailer[i]->next;

  return trailer[(i+FOUR)%FIVE];  
}

Nth Node from end.

#include <stdio.h>
#include <malloc.h>

typedef struct list{
struct list *next;
int val;
}list;
list *root;
void alloc(list **node, int val)
{
*node = (list *)malloc(sizeof(list));
(*node)->val = val;
(*node)->next = NULL;
}

void BuildList()
{
list *temp = root, *end=NULL;
int i=0, len;

printf("Enter the number of numbers:");
scanf(" %d",&len);
if(len >0)
alloc(&root, i+1);

for(i=1;i<len;i++)
{
alloc(&temp,i+1);
if(root->next == NULL)
{
root->next = temp;
end = temp;
}
else
{
end->next = temp;
end = temp;
}
}
}

void PrintList()
{
list *temp= root;

while(temp != NULL)
{
printf(" %d", temp->val);
temp = temp->next;
}
printf("\n");
}
void nthFrmLastNode(int nth)
{
int n=nth;
list *nthnode=root, *temp = root;

if(n<=0)
{
printf("Invalid Input\n");
return;
}
while(n > 1 && temp != NULL)
{
temp = temp->next;
n--;
}
if (n >= 1 && temp == NULL)
{
printf("There doesnt exist Enough nodes to find the %dth node\n", nth);
return;
}
else if (n<1 &&temp->next == NULL)
printf("%d node is %dth node\n",nthnode->val, nth);

while(temp->next != NULL)
{
temp=temp->next;
nthnode = nthnode->next;
}
printf("%d node is %dth node\n",nthnode->val, nth);

}

int main(void)
{
int nth;
BuildList();
PrintList();
printf("Enter the nth node u want to know:");
scanf(" %d",&nth);
nthFrmLastNode(nth);
return 0;
}

int nthNode(list *temp, int n)
{
    int nth;
    if(temp->next == NULL)
        return n-1;
    nth = nthNode(temp->next, n);
    if(nth == 1 )
    {
        printf("The nth Node has %d value\n", temp->val);
        return 0;
    }
    else
        return nth-1;
}

int main(void)
{
    int nth;

    printf("Enter the nth node u want to know:");
    scanf(" %d",&nth);

    nth = nthNode(root, nth);
    if(nth > 0 )
        printf("There doesnt Exist Enough Nodes\n");
    return 0;
}

node * nthelement ( node ** head, int n )
{
Struct * curr, *backhead;
Curr= head;
Backhead = *head;
While(int i>=0)
{
Curr = curr->next;
n--;
}
While(curr->next)
{
Backhead= backhead->next;
}
Return backhead;
}

void mthLastElement(Node **head, int m)
{
    Node *cur = *head, *ptr = *head;
    int pos = 1;
    while(pos <= m && cur!=null)
    {  cur = cur->next;  pos++; }
    if(cur==null)
      return -1; //invalid m
    while(cur != null)
    {     cur = cur->next; ptr= ptr->next; }
    printf("mth last node = %d", ptr->data);
}

A modified problem: print every m-th element from the last of the linked list.
A recursive solution:

int traverse (struct node *cur, int m)
{
	if (cur == NULL) return 0;
	
	int count = 1 + traverse (cur->ptr, m);
	if ( count%m == 0) cout << cur->data << "  ";
	return count;
}

<pre lang="java" line="1" title="CodeMonkey61004" class="run-this">i
/*Remove nth element from end.
Use two pointers at a difference of n. Once the farthest point is at
ens I am done.
*/

ListNode nthElement(ListNode head, int n)
{
ListNode curr = head;
ListNode far = head;
while(n-- > 0){
if(far != NULL)
far = far->next;
}
if(n>0 || far == NULL)
return NULL;
while(far != NULL) {
curr = curr->next;
far = far->next;
}
if(curr != NULL)
return curr;
else
return NULL;
}


</pre><pre title="CodeMonkey61004" input="yes">1
2
10
42
11

</pre>

What do you thing regarding this approach.

1. Count length of the linkedlist.
2. Actual Node index from head = linkedlist length - given index;
3. Write a function to travesre from head and get the node at the above index.

@Rahul
That ways you are traversing the list twice. The best solution is to have 2 pointers with n nodes difference i.e., p1 is n nodes ahead of p2. And when p1 reaches end, p2 gives the nth node from the rare end.

int 5thfromlsat(List L)
{
int count=0;
Node current=L,temp=L;
while(temp!=null)
{
if(Incr(&count)==6)
current=current->next;
temp=temp->next;
}
if(count==6)
return current;
else
return null;
}


int Incr(int *x)
{
if(*x!=6)
{
*x=*x+1;
return *x;
}
else
return *x;
}

List 5thfromlsat(List L)
{
int count=1;
Node current=L,temp=L;
while(temp->next!=null)
{
if(Incr(&count)==6)
current=current->next;
temp=temp->next;
}
if(count>=5)
return current;
else
return null;
}

int Incr(int *x)
{
if(*x!=6)
{
*x=*x+1;
return *x;
}
else
return *x;
}

This is the simplest I could get it to:

Node* NthLastElementList(Node* list, int n)
{
    Node* p = list;
    while (p && n != 0)
    {
        p = p->next;
        n--;
    }
    if (n != 0)
    {
        return NULL;
    }
    else
    {
        while (p)
        {
            p = p->next;
            list = list->next;
        }
        return list;
    }
}

(1) Say we have a very big single linked list having 200 nodes.
(2) Consider two node pointers p and q. Initially p will point to the first node of the list and q will point to the 5th node of the list
(3) Start traversing both p and q one node at a time.
(4) Once q will reach to NULL (TAIL of the list), return p.

import java.util.*;
public class Find5thElementFromASinglyLinkedList
{
public static void main(String args[])
{
Scanner in = new Scanner(System.in);
int n = in.nextInt();
LinkedList<Integer> list = new LinkedList<Integer>();
list.add(2);
list.add(5);
list.add(3);
list.add(10);
list.add(7);
list.add(6);
list.add(12);
list.add(14);
list.add(21);
list.add(18);
list.add(11);
list.add(15);

if(list.size() == 0)
System.out.println("List is empty");
else if(list.size() < n)
System.out.println("position given is greater than size of the list");
else
System.out.println("The "+n+"th element of the list is "+list.get(list.size() - n));
}
}