CareerCup

ve just posted some interveiw questions.Does anyone out there have a clue to the solutions?

NODE element_from_end(NODE head,int n)//n is the element from last here it is 5
{
NODE ptr1,ptr2;
ptr1=ptr2=head;
for(int i=0;i<n&&ptr1;i++)
ptr1=ptr1->next;
while(ptr1)
{
ptr1=ptr1->next;
ptr2=ptr2->next;
}
return ptr2;
}

Sample Test Cases:
Make combinations of List and N

List: Empty, 1 element, 10 elements, circular.
N: negative, 0, positive, 1, 2, 9, 10, 11.

Node *ReturnNthNode(Node *phead, int n)
{
	Node *pCur = phead;
	
	for(int i=1; i < n && pCur; i++)
	    pCur = pCur->next;

	if(NULL == pCur)
	{
	    return NULL;
	}

	while(pCur->next)
	{
	    pCur = pCur->next;
	    phead = phead->next;
	}

	return phead;
}

int nthNodeFinder(int n, node inPtr) {
node *front, *nthBack;
int ctr = 0;

front = nthBack = inPtr;

while (front != null && ctr++ < n) {
front = front->next;
}

if (ctr <= n)
return;

while (front != null) {
nthBack = nthBack->next;
front = front->next;
}

return nthBack;
}


table of test cases


test case #, LL Length, N
1 | 0 | 4
2 | 1 | 4
3 | 1 | 1
4 | 3 | 2
5 | 12 | 5
6 | 9 | 0

node* getNodeFromLast(node *root,int m){
      int ckt = 0;
      node *element = NULL;
      node *first = root;
      while(root != NULL){
                 root = root->next;
                 ckt+=1;
                 if(ckt == m){
                        element = first;
                 }
                 if(ckt>m){
                           element = element->next;
                 }
      }
      return element;

}

We could use recursion
In the recursive function call the next node till the end of the list
When the stack is unwinding, use a counter to determine when you have reached the correct node.
The reasoning is that the last node will be processed first, then the second last, then the third last and so on

We could use recursion
In the recursive function call the next node till the end of the list
When the stack is unwinding, use a counter to determine when you have reached the correct node.
The reasoning is that the last node will be processed first, then the second last, then the third last and so on

We can push all the elements to the stack, then pop the stack 5 times in general n times to get the nth element from the tail.

takes two pointer p1 and pn where "n" indicate which no. of node from end intially both are intiallized by head node of LL
First move "pn" to n node ahead to p1
if pn == null then return list is less length then n
else
move pn and p1 one step ahead one by one until pn = null
at the end p1 will point nth node from end
ex. n =5 ;
1 -> 2 -> 3 -> 4 -> -> 5 -> 6 -> 7
p1 = 1 and p5 = 5
p5 = 6 so p1 = 2
p5 = 7 so p1 = 3 and p5 = null stop ....and p1 is the 5th node from the end .... :)

test cases
1> list is empty 2> list has less no. of nodes then "n"
3>list is circular 4> list has equal no. of node of "n" 5> list has more than "n" nodes
6> list has only one node 7> list has only one node with circular fashion