CareerCup

I think it is not possible to get -nth pointer from some node in single linked list, because you have only pointer to the next node, but no pointer to previous.

If you want -nth from there is possible to traverse list from the begin, remember n previous adresses and lineary search the list for the input node, but this is little bit complicated...

for nth node from the list its straight forward
But for -nth,instead of reversing the list and again setting it back.We can break the list and make it a circular list,find the nth last element in that circular list. And later revert back the changes

Ex:

1-2-3-4-5-6-7-8 is the linked list
return N(4,-2)

break the list at 4 and connect the next pointer of 4 to 1
now u have a list 1-2-3-4-1...

now from 1 find the 2nd last element using the mth last element algo with some modification in the termination condition

and now connect 4 back to 5

Since when did IBM start asking such Qs. As far as I knw, it asks only some silly HR Qs.!!

It can be that second operation has to be performed on the list resulted in first op.

If so, second returnN(4,-2) is also simple same as first. Traverse from the list node 4, swap the links to do the reverse linked list checking for the count.

Can not guarantee the (-n) part. You can try:
given ptr;
prev_pointer = (struct single_lnk_lst *) (ptr-(sizeof (struct single_lnk_lst) * 2));
if(single_lnk_lst->next == ptr) // you are lucky to get to -1, now do that n more times.

For -ve, if an extra memory is allowed, its simple. If we are calling the method with (M,N) Push the elements till Mth node onto the stack and pop the N elements then you will get the m-nth element as top of the stack.

public void getelement(int p, int d){
	node n = head;
	int count = 0;
	while(n.val != p && n != null){
		if(n.sibling == null){
			System.out.println("enter correct input");
			System.exit(0);
		}
		else{
			count++;
			n = n.sibling;
		}
	}
	if(d > 0){
		while(n != null && (d-- > 0)){
			if(n.sibling == null){
				System.out.println("cant move. enter correct input");
				System.exit(0);
			}
			else{
				n = n.sibling;
			}
		}
		System.out.println(n.val);
	}
	else{
		int k = count+d;
		if(k < 0){
			System.out.println("cant move. enter correct input");
			System.exit(0);
		}
		node res = head;
		while(res != null && (k-- > 0)){
				res = res.sibling;
		}
		System.out.println(res.val);
	}
}

Best solution:-

There is a head node denoted by list *head.
list * returnN (list *node, int n)
{
   Take 2 pointers p1 & p2, make them both point to head.
   Now if n<0, 
      Keep forwarding one pointer p1 to right for |n| times, where |n| = abs(n)
      Now forward both the pointers until p1 reaches node.
      return p2.
   Else if n>0,
      p1 point to node.
      Just keep forwarding p1 to right for n times.
      return p1.