k'th Node from End

Given a linked list and a positive integer k, write a function which will return value of k’th node from the end of list. If Linked list is

2 -> 4 -> 6 -> 3 -> 7

and k=2, then output should be 3 (2^nd node from end).

Solution:

Method-1: Brute force method:

The brute force approach is to traverse the list twice. Calculate the total number of nodes in the first pass, say N, Now you have to print the (N-k)th node from the start of the list. Below function does this

    node * findFromEnd(node * head, int k)
    {
        if(k<0 || !head) { return NULL; }
        node * val = NULL;
        int N = 0;
        /* Calculate the total number of nodes in list,
         * val is assigned head to avoid using another temporary object.
         * we cannot change head because we will loose a pointer to the first node */
        // Empty loop
        for(val=head; val; val=val->link; N++);
        val = NULL;
        // Empty loop
        for(int i=0; i<N-k; i++) val = val->link;
        return val;
    }

Method-2: Extra Pointer method:

Maintain 2 pointers A & B both initialized to the head of the linked list. Move A ahead of B so that A points to the k’th element (from start of the list). Now move both the pointers ahead, one node at a time till A reaches the end of the list.

When A is at the end of the list B will be pointing to the k’th node from the end of the list.

Code:

    node * findFromEnd(node * head, int k)
    {
        if(k<0 || ! head)
            return NULL;
        /* we will have only one pointer, head pointer will act as the second pointer */
        node * A = NULL;
        for(int i=0; ilink);
        /* Case – list has less than k elements */
        if(!A)
            return NULL;
        while(A->link)
        {
            A = A->link;
            head = head->link;
        }
        return head;
    }

Time Complexity of both the above methods is O(n), where n = number of nodes in the linked list.