Finding the "Nth node from the end" of a linked list.

Question

This seems to be returning the correct answer, but I'm not sure if this is really the best way to go about things. It seems like I'm visiting the first n nodes too many times. Any suggestions? Note that I have to do this with a singly linked list.

Node *findNodeFromLast( Node *head, int n )
{
    Node *currentNode;
    Node *behindCurrent;
    currentNode = head;
    for( int i = 0; i < n; i++ ) {
        if( currentNode->next ) {
            currentNode = currentNode->next;
        } else {
            return NULL;
        }
    }

    behindCurrent = head;
    while( currentNode->next ) {
        currentNode = currentNode->next;
        behindCurrent = behindCurrent->next;
    }

    return behindCurrent;
}

Answer 1

You could use a doubly linked list, which is a linked list that also stores the address of it's parent. Transversal is much easier, since you can start at the end and work your way to the beginning.

Answer 2

Your running time is still O(n), so I don't see that there's any problem with it.

Conceptually, you can divide the list into two parts: the part before the node you're returning, and the part after. One of these parts will have to be walked twice. Your implementation has chosen the first, at the advantage of no extra memory use (other than a couple temporary variables).

Alternatively, you could create a stack, walk the list and put each element into the stack, and then pop off n items. Then you'd be walking the end of the list twice, instead of the beginning. This has the disadvantage of storing the list in memory twice. (You could make the stack a little smarter by only storing n elements and dropping them off the bottom of the stack as new ones are added; then you're only using enough space to store n Nodes.)

I'm assuming that you can't blow away the list by reversing it in place. Then it's constant memory, still O(n), still walking the end of the list twice.

Answer 3

Start an two pointers. Move the first one N elements ahead and then move each pointer 1 element. When the first pointer reaches the end, second pointer will give the answer.

EDIT : Yes, it is pretty much the same code as given in the question. But I feel the pseudo code make it clearer. To answer the question, there is no other go as first N elements have to be visited twice. If N is small it doesn't matter. If N is large then the second loop will be small. So it is always an O(n) solution.

Answer 4

First count the number of nodes in the list. Then traverse again, counting off n less nodes. Still an O(n) algorithm, that's unavoidable.

Answer 5

Another way to do it without visiting nodes twice is as follows:

Create an empty array of size n, a pointer into this array starting at index 0, and start iterating from the beginning of the linked list. Every time you visit a node store it in the current index of the array and advance the array pointer. When you fill the array, wrap around and overwrite the elements you stored before. When you reach the end of the list, the pointer will be pointing at the element n from the end of the list.

But this also is just an O(n) algorithm. What you are currently doing is fine. I see no compelling reason to change it.