Find Mth to last node on a singly liniked list...

[stingBlah]

I have a question on which algorithm is more efficient (time & space) on solving this singly linked list problem:

#1:
Have one pointer go through and find the size of the list,
have another go through until it is at node size-m

#2:
Have one pointer go up to the mth node,
now have another pointer start at first node;
increment both pointers until the first has reached the end. The second one is now at the mth to last node.

Would #2 be faster than #1, or would they be of the same speed?


Also, for the following function which implements alg.#2, instead of initializing a second pointer, could I just use head?

Node *mToLast( Node *head, int m)
{
    Node *first;      //Do I need Node *second ?
    int count;
    while (count != m) {
        first= first->next;
        count++;
    }
    while (first != null) {
        first= first->next;
        head= head->next;     //Can I use head like this?
    }
    return head;
}

Also, when the above function is finished, the original head node pointer (which was passed in) will be unchanged, right? (because only a copy of the pointer is being passed into the function...)


thank you very much!

[stingBlah]

would including another node pointer (Node *second;) take up more space? Since this is just a pointer variable, I don't think it would take up that much space, so should that be a concern when implementing the algorithm (to minimize pointer variables used). Also, would the number of integers in the algorithm use much space? I feel having an "int count" wouldn't be a point of concern.

Thanks!

[firedraco]

I'm not completely sure what you mean on #2 by:

now have another pointer start at first node;
increment both pointers until the first has reached the end. The second one is now at the mth to last node.

Do you mean that the second pointer will start at head and then you will increment them both till the second one is at the end? In that case, that wouldn't even work.

Couldn't you just do something like this?

unsigned int count = 0;
Node* start = head, end; //initializing stuff
while(count != m && start) { //while count isn't what we want and start is not NULL
    start = start->next; //go to the next node
    ++counter;
}
end = start; //make end the same as start, since start is now at wherever the "start" of m-end is
while(end->next) { //simply move end to the end of the list here
    end = end->next;
}
return /*whatever*/;

And to answer your question:
Yes.

[stingBlah]

I believe your code finds the mth node from the BEGINNING. My question dealt with the mth node from the END. So when m=0, the last node is returned. If m=1, the second-to-last node is returned, and so on.

For #2, I basically want 2 pointers spaced m nodes apart. When the first one reaches the end, the second pointer will be m nodes away from the end, which is exactly what I want.

Also, which question did you answer "yes" to?

Thanks!

[Duthomhas]

As a general solution, #2 is best.
Make sure to handle the possibility that the list is < m nodes long.
Good luck!

[jsmith]

I think in either case the number of pointer chases is ( size + size - m ), meaning
that the two algorithms are identical in runtime efficiency.

[Disch]

You shouldn't have to loop through the list more than once:

firedraco was on the right track but I don't think he thought it through all the way.

Node* MthFromEnd(int m)
{
    // assuming 'm' is the 'mth from the end'
    //  ie:  0 would return the last node
    //  this function returns 0 if m >= listsize
    //  otherwise it returns the appropriate node

    Node* node = head;
    for(int i = 0; i < m; ++i)
    {
        if(!node)
            return 0;   // not large enough
        node = node->next;
    }

    Node* mth = head;
    while(node)
    {
        mth = mth->next;
        node = node->next;
    }

    return mth;
}