k'th Node from End of a Linked List

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

Solution:

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;
    }

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 (Move the Window), 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.