Home > Applied Algorithms, Linked List > Find the nth node from the end in a linked list.

Find the nth node from the end in a linked list.

Today we have a very easy one in our hands. The problem statement asks you to find the nth from last node. How do you plan to do this?

Some of my friends said, “We’ll move through the whole linked list once, and calculate its length. Then we’ll start over and go to length-nth node”. Well, yeah. You can certainly do that and the time complexity will be O(n). However you are traversing the whole linked list twice which is not advisable. You can instead finish this task in one traversal of the linked list.

Can you make a guess? Well, here’s how it will be done:

Take 2 pointers both pointing at START. Now move the second pointer forward to the nth node (from start). Next, you start moving both these pointers forward by 1 node at a time. So we are maintaining a separation of n nodes between our two pointers. As soon as your second pointer reaches the end of the linked list, you can say that the first pointer is currently at the nth node from the end.

Sly, eh?! Have fun with this new algorithm! 🙂

Advertisements
  1. May 3, 2014 at 3:08 am

    I really like the 2 pointer approach. But there is a recursive solution to this as well as written here – http://k2code.blogspot.in/2010/04/return-nth-node-from-end-of-linked-list.html:

    node* findNthNode (node* head, int find, int& found){
        if(!head) {
            found = 1;
            return 0;
        }
        node* retval = findNthNode(head->next, find, found);
        if(found==find)
            retval = head;
        found = found + 1;
        return retval;
    }
    

    Thanks.

    • December 5, 2014 at 10:51 am

      While I haven’t gone over the correctness of the code you wrote, I agree that a recursive method is possible and suggested in multiple places on the internet. I would strongly discourage using recursion whenever it can be avoided, since recursion pushes each function execution state onto the stack which is highly memory intensive.

  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: