Friday, May 25, 2007

Write a C program to return the nth node from the end of a linked list.

Here is a solution which is often called as the solution that uses frames.

Suppose one needs to get to the 6th node from the end in this LL. First, just keep on incrementing the first pointer (ptr1) till the number of increments cross n (which is 6 in this case)


STEP 1 : 1(ptr1,ptr2) -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10

STEP 2 : 1(ptr2) -> 2 -> 3 -> 4 -> 5 -> 6(ptr1) -> 7 -> 8 -> 9 -> 10



Now, start the second pointer (ptr2) and keep on incrementing it till the first pointer (ptr1) reaches the end of the LL.


STEP 3 : 1 -> 2 -> 3 -> 4(ptr2) -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 (ptr1)


So here you have!, the 6th node from the end pointed to by ptr2!


Here is some C code..


struct node
{
int data;
struct node *next;
}mynode;


mynode * nthNode(mynode *head, int n /*pass 0 for last node*/)
{
mynode *ptr1,*ptr2;
int count;

if(!head)
{
return(NULL);
}

ptr1 = head;
ptr2 = head;
count = 0;

while(count < n)
{
count++;
if((ptr1=ptr1->next)==NULL)
{
//Length of the linked list less than n. Error.
return(NULL);
}
}

while((ptr1=ptr1->next)!=NULL)
{
ptr2=ptr2->next;
}

return(ptr2);
}

29 comments:

Ankit said...

good solution man

Anonymous said...

one could reverse the list and start...

viagra prescription said...

Hello people want to express my satisfaction with this blog very creative and I really like the views of the focus very good indeed Thank you for the helpful information. I hope you keep up the good work on making your blog a success!

Unknown said...

Try it!!!

int nthnode(struct node *p, int n)
{
if( p == NULL)
return 0;
else
{
int x = 1+nthnode((p->next),n);
if( x == n)
cout<<"Nth Element: "<i<<endl;
return x;
}
}

Thanks,
Chandra

Unknown said...

int nthnode(struct node *p, int n)
{
if( p == NULL)
return 0;
else
{
int x = 1+nthnode((p->next),n);
if( x == n)
cout<<"Nth Ele: "<i<<endl;
return x;
}
}

Unknown said...

int nthnode(struct node *p, int n)
{
if( p == NULL)
return 0;
else
{
int x = 1+nthnode((p->next),n);
if( x == n)
{
cout<<"Nth Ele: "<<
p->i<<endl;
}
return x;
}
}

Palmer Eldritch said...

Can be optimized easily, instead of using two loops - merge them into one by adding one condition which checks counter.

As alternative solution - one can first count the length of LL, and then search for (count - n)th element.
second alternative is reversing LL and get nth element from the start of LL.

idoser viagra said...

Thanks for the nice blog. It was very useful for me. Keep sharing such ideas in the future as well. This was actually what I was looking for, and I am glad to came here! Thanks for sharing the such information with us.

online name brand viagra said...

I liked this blog, i think is very interesting, most of all for the new ideas that this blog talk.

Anonymous said...

wonderful posts....

viagra said...

Your blog is outrageous! I mean, Ive never been so entertained by anything in my life! Your vids are perfect for this. I mean, how did you manage to find something that matches your style of writing so well? Im really happy I started reading this today. Youve got a follower in me for sure!

Ao Zhang said...

Great solution!

Ao Zhang said...
This comment has been removed by the author.
Anonymous said...

oZzy moved away some time ago, I miss his cock, and i am always hungry for sex.


FUCK MY PUSSY!

Here is my blog post :: hcg injections

Anonymous said...

Though, you are among those who lack of plus compare accommodation what customer, loan that can help you pay for every item that you have recently been missing out on. Typically, you can either walk out while using money in your hand or have the item after the final decision has been made comprehend or so. For anyone borrowers exactly who truly possess bad credit, tenant customer there desperately and also explain your problem? instant same day loans This can help show you real life expertise that will be a good choice for the rest of your existence.

Anonymous said...

Among the finest ways to construct a good romantic relationship with your mortgage broker is to converse! Many lenders tend to be associated with this specific popular manner with different financial loan quotes! You are likely to repay the financial loan money along with interest priced within a quick and flexible amount 14-31 days! click here Many lenders provide on-line services to make available car loans for kids!

Anonymous said...

buy tramadol 100mg tramadol codeine high - tramadol hcl withdrawal

Anonymous said...

The Canon refurbished cameras are able to provide this quality and reliability because they have been checked, repaired and serviced by their manufacturers.
Red lights can be tricky but can be made to
look good if you're careful. On the other hand, the Nano worked fine, but after a couple of hours of steadicam work, my arms were getting tired.

Here is my webpage: canon eos 6d

Anonymous said...

They (Sony) purchased Crackle for a reputed
$65 million in 2006, just prior to Google's $1. However, we can't choose
our favorite program and movie when we watch TV. You can
edit and set for conversion here, such as file and title name, bit rate, frame
rate, file size, frame resolution, aspect ratio, volume, and so on.


my web blog ... apple tv review

Anonymous said...

You can get the older digital Canon Rebel, with a lens, for a good price new.
Of course, doing backup is the best way to avoid image loss.
Nikon the digital camera giant has recently added one more exquisite DSLR camera to its latest camera family.



My web-site; nikon d7100

Anonymous said...

What i don't realize is actually how you are no longer actually much more well-liked than you might be right now. You are so intelligent. You already know thus considerably in relation to this subject, made me in my opinion imagine it from a lot of numerous angles. Its like men and women are not involved unless it's one thing to accomplish with Girl gaga!
Your personal stuffs nice. Always take care of it up!



Here is my site hsdgfuyewertwe.com

Anonymous said...

Appreciate the recommendation. Will try it out.

Here is my homepage - reputation management for individuals

Anonymous said...

That being said, it can be seen that Apple and Samsung continue to
grab market share from other OEMs. The application Execution Environment provides an interface for application programming.
However, they are less likely to say these tools helped them
save money at a rate of 44 percent to 49 percent.

Here is my blog; samsung galaxy s4

Anonymous said...

This article will help you find the best tablet
PC. 9 is also razor thin with the same great features as the Galaxy Tab 10.
Samsung galaxy has been developed as a star model that is available at best bargain deals.


Feel free to visit my web-site samsung galaxy tab 2

Anonymous said...

However, there is high internet access on the phone and there are all possibilities of a virus attack on the phone.
Another deal offering LCD as gift item covers a tariff offering.

i - Phone application developers and Apple app store still holds unmatchable number of
apps in terms of quality.

Also visit my weblog - samsung galaxy s4

Anonymous said...

If you want to meditate with your Black - Berry using the resources already installed on
the phone, there are a variety of ways you can do this:.

I can hook up to the internet several ways - with the wireless
ability it's, or tethering for you to my cellphone or, if you've got
a Blackberry working version 5 as well as above
you should use the Fill to access the net while
about. You will get amazing discounts and thus saving your money.



My website ... blackberry playbook

Anonymous said...

Ι alωays uѕed tо read аrtіcle in news
paρers but now as I am a user of web sο from now I am using net for posts, thanks to web.


Нere is my homepage - reputation management

Anonymous said...

There are a great amount of channels to choose from including CNN, Amazon Instant Video, HBO GO, Crackle, MLS Game Day, music from Pandora, play games
and more. Blip - TV: Distributes 48,000 independently-produced Web shows.

Apple TV and Roku are two devices you can use to stream High Definition (HD) Video, movies, TV
Shows, photos, and more to your HD TV wirelessly and connect to your wireless environment and connect to the internet.


Here is my web blog roku 2 xs

Kinshuk Chandra said...

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