Jun 132012
 

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 (2nd 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.

 Leave a Reply

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

(required)

(required)