Linked List: Find n-th element from the tail

Question: Given a singly linked list find the n-th node from the back.

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
}

2 comments:

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

    ReplyDelete
  2. Hi 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.

    While 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.

    ReplyDelete