Solution 1: Reverse the linked list and select the n-th node from the head of the linked list.

Solution 2: Maintain 2 pointers n nodes apart. When the 1st pointer reaches the tail, the second pointer will be pointing to the desired node.

Notes: Both solutions take O(n) time but Solution 2 is more elegant.

Code:

//define the list node typedef struct _node { int i; struct _node *next; } Node; Node * FindNthFromBack(Node *listHead, int n) { Node *ptr1, *ptr2; // we need 2 pointers ptr1 = ptr2 = listHead; // set the pointers to point to the list head initially while(ptr1->next != NULL) // keep looping until we reach the tail (next will be NULL for the last node) { if(n > 0) { ptr1 = ptr1->next; //increment only the 1st pointer n--; } else { ptr1 = ptr1->next; //increment both pointers ptr2 = ptr2->next; } } return ptr2; //now return the ptr2 which points to the nth node from the tail }

it should be return ptr2->next or while (ptr1 !=null)

ReplyDeleteHi ACR, I was assuming the last node to be the 0th node from back. But, if one assumes the last node to be treated as the 1st node from back then we would have to do what you suggested above.

ReplyDeleteWhile looking at the code above I did notice that n is an int, so the code would always return the last node. We would have to do some special case handling, if n is negative, to either take the absolute value of n or return the nth node from front.