Thursday, May 24, 2007

How do you find the middle of a linked list? Write a C program to return the middle of a linked list

Here are a few C program snippets to give you an idea of the possible solutions.


Method1 (Uses one slow pointer and one fast pointer)


#include
#include

typedef struct node
{
int value;
struct node *next;
struct node *prev;
}mynode ;



void add_node(struct node **head, int value);
void print_list(char *listName, struct node *head);
void getTheMiddle(mynode *head);

// The main function..
int main()
{
mynode *head;
head = (struct node *)NULL;

add_node(&head, 1);
add_node(&head, 10);
add_node(&head, 5);
add_node(&head, 70);
add_node(&head, 9);
add_node(&head, -99);
add_node(&head, 0);
add_node(&head, 555);
add_node(&head, 55);

print_list("myList", head);
getTheMiddle(head);

getch();
return(0);
}




// This function uses one slow and one fast
// pointer to get to the middle of the LL.
//
// The slow pointer is advanced only by one node
// and the fast pointer is advanced by two nodes!

void getTheMiddle(mynode *head)
{
mynode *p = head;
mynode *q = head;

if(q!=NULL)
{
while((q->next)!=NULL && (q->next->next)!=NULL)
{
p=(p!=(mynode *)NULL?p->next:(mynode *)NULL);
q=(q!=(mynode *)NULL?q->next:(mynode *)NULL);
q=(q!=(mynode *)NULL?q->next:(mynode *)NULL);
}
printf("The middle element is [%d]",p->value);
}
}



// Function to add a node
void add_node(struct node **head, int value)
{
mynode *temp, *cur;
temp = (mynode *)malloc(sizeof(mynode));
temp->next=NULL;
temp->prev=NULL;

if(*head == NULL)
{
*head=temp;
temp->value=value;
}
else
{
for(cur=*head;cur->next!=NULL;cur=cur->next);
cur->next=temp;
temp->prev=cur;
temp->value=value;
}
}



// Function to print the linked list...
void print_list(char *listName, struct node *head)
{
mynode *temp;

printf("\n[%s] -> ", listName);
for(temp=head;temp!=NULL;temp=temp->next)
{
printf("[%d]->",temp->value);
}

printf("NULL\n");

}


Here p moves one step, where as q moves two steps, when q reaches end, p will be at the middle of the linked list.





Method2(Uses a counter)


#include
#include

typedef struct node
{
int value;
struct node *next;
struct node *prev;
}mynode ;



void add_node(struct node **head, int value);
void print_list(char *listName, struct node *head);
mynode *getTheMiddle(mynode *head);

// The main function..
int main()
{
mynode *head, *middle;
head = (struct node *)NULL;

add_node(&head, 1);
add_node(&head, 10);
add_node(&head, 5);
add_node(&head, 70);
add_node(&head, 9);
add_node(&head, -99);
add_node(&head, 0);
add_node(&head, 555);
add_node(&head, 55);

print_list("myList", head);
middle = getTheMiddle(head);
printf("\nMiddle node -> [%d]\n\n", middle->value);

getch();
return(0);
}


// Function to get to the middle of the LL
mynode *getTheMiddle(mynode *head)
{
mynode *middle = (mynode *)NULL;
int i;

for(i=1; head!=(mynode *)NULL; head=head->next,i++)
{
if(i==1)
middle=head;
else if ((i%2)==1)
middle=middle->next;
}

return middle;
}


// Function to add a new node to the LL
void add_node(struct node **head, int value)
{
mynode *temp, *cur;
temp = (mynode *)malloc(sizeof(mynode));
temp->next=NULL;
temp->prev=NULL;

if(*head == NULL)
{
*head=temp;
temp->value=value;
}
else
{
for(cur=*head;cur->next!=NULL;cur=cur->next);
cur->next=temp;
temp->prev=cur;
temp->value=value;
}
}


// Function to print the LL
void print_list(char *listName, struct node *head)
{
mynode *temp;

printf("\n[%s] -> ", listName);
for(temp=head;temp!=NULL;temp=temp->next)
{
printf("[%d]->",temp->value);
}

printf("NULL\n");

}




In a similar way, we can find the 1/3 th node of linked list by changing (i%2==1) to (i%3==1) and in the same way we can find nth node of list by changing (i%2==1) to (i%n==1) but make sure ur (n<=i).

93 comments:

Anonymous said...

u are doing a very good job....but can u please try it in c# also...that would be great

Anonymous said...

Airline Tickets: Make Some Time to Save Some Money


When people decide to travel, the last thing that in general crosses their mind has to do with airline tickets. In general, people are so anxious to take the trip that they establish the destination, choose the hotel, look for tourism packages and even sometimes rent a car and the airline ticket is forgotten.

Airline companies know about that and they can do many things just to create strategies to get the biggest profits they can from the buyer. The only way to prevent this from happening is to dedicate some time before travelling just looking for different companies that offer tickets to the destination you want, and comparing the prices.

Saving some money

Have you ever given up on a trip because the airline ticket was a fortune you couldn't afford? Yes, this is a pretty common thing and it happens more than we imagine. There are people that plan the whole trip, choose the place, the hotel, buy special clothes for the destination, and when it's time to buy the airline ticket, simply find out they cannot afford it.

In order to avoid that, rather than planning everything in advance and leaving the airline tickets for last, do the opposite. Airline tickets should be at the head of the list of things to do for someone who is going to travel.

It's important to have some guidelines to buy cheaper tickets and save some money to spend on the trip. Some useful things are:

- Write a small list of places you would like to go to. After that, start looking for airline companies that offer flights to those places.

- When this is done, it's time to check your budget and establish how much you are willing to spend. This is pretty helpful because it avoids frustration. It's easier to travel if you have more than one option because you can have different prices to choose from and see which one best fits in with your own budget.

- If you are used to travelling on business, you can check on discounts, either with a travel agency or with the company you are using.

- Sometimes, travelling with a tourist package is cheaper than planning your trip by yourself. This happens because agencies offer packages that include airline tickets, hotels, sightseeing, visits to landmarks, car rental and some other things.

Different prices - Same arrival

Since there are many airline companies spread through the world, people can find several prices if they look at different airlines. The competition in this market is so tough that the difference between prices can be enormous.

However, if you are used to always travelling with the same company, you probably have some sort of bonus program that offers discounts. In this case, it's advisable for you to check the deals that may be available to the destination you've chosen, before going looking for tickets with other companies.

Holidays and airline tickets

If you have all the details of your holiday settled, buy your ticket in advance. Besides avoiding a rise in the price, you don't run the risk of tickets for your destination being fully booked.


To search for the best deals for airline tickets please visit [url=http://airlineplace.com]Airline Tickets[/url] website.

Anonymous said...

[b] The New Space Saver, Futon Bunk Beds - How To Choose The Right Mattress For You [/b]

Futons, a Japanese creation, can be found in dorm rooms and spare bedrooms across the country. Futons are popular largely because of their functionality, since they can easily convert from a couch to a bed and back again while taking up very little space. If you're looking to buy a futon, there are a few things you should keep in mind.

Futon frames can be found in a variety of styles and materials and will vary between manufacturers. Higher quality futon frames are made of wood and have many wooden support slats placed close to each other. This provides and even and comfortable support and prevents the mattress from sagging between the slats, which can be very uncomfortable and lead to back problems. Less expensive futons are made of metal but can still be very durable and comfortable. Keep in mind when looking to buy a futon where you will be putting it. Futons come in various sizes and styles with some needing to be pulled away from the wall in order to convert into a bed.

Higher quality futons will come with a higher quality mattress. Typically, futon mattresses can range in thickness from 4 to 8 inches, with the thicker mattresses being more comfortable. Also keep in mind the mattress material when considering comfort. As futons gain in popularity, many traditional mattress makers are getting into the futon business by selling innerspring futon mattresses. While these mattresses may provide more comfort when used as a bed, they are often awkward when the futon is in the couch position. In order to match your style and decor, there are many different styles of futon covers to place over your futon mattress

The reason futons have become so popular is that they can serve many purposes. They can provide you a cheap couch for your dorm or spare bedroom that easily converts to a bed for when you have guests spend the night.


The biggest choice of beds and mattresses on [url=http://best-beds.com]Best Beds and Mattresses Website Best-Beds.com[/url]. Pick the bed that suits you best!

Anonymous said...

[b]Things To Consider When Buying A Used Car[/b]


You are ready to buy a used car? Make sure you know certain things about cars because there are dealers or even private people who try to sell cars overpriced or even damaged ones. This article deals with several details that you want to consider before buying a used car.

Always have a closer look at the car before buying it. This includes several parts of the car that we will discuss right here.

1. The mileage

An older car will have a higher mileage but sometimes you can find cars that were driven for less than 5000 miles a year. An average consumer will drive between 12,000 and 16,000 miles a year. Those cars with a high usage are usually those that won't make you happy.

2. Inspect the engine

Have somebody with you who knows a lot about cars because the engine of a car is the most important thing to look at before buying the vehicle. A good clean looking engine is not always an indicator for a good working engine. The owner might have washed it just to achieve a higher price for the car.

Always test drive the car, this way you might find a technical problem. People who know a lot about cars can sometimes tell, just from hearing the engine sound, if the engine is alright or not.

3. Check the body of the car

Look for rusty areas and damages, check the whole body of the car. Look at areas near the bottom, these are the places where the rust spreads first.

4. Frame damages

Make sure that the car did not have an accident. Some car dealers try to sell a damaged cars, sometimes even with frame damages. These can be very dangerous for the new owner, so check the car carefully.

5. The Tires

Make sure all 4 tires are in a good condition. Look at the profile and check if the material is in a smooth condition. Make sure there aren't any damages at the tires, they are your life insurance!

6. Safety Features

Some old cars don't meet today's safety standards. It is up to you what level of safety standard you choose with your used car, just make sure the ones that are included work.

7. The price

Before buying a car, you want to compare the prices for the car model that you desire. You can use the internet for this issue. This way you can protect yourself from overpriced car deals. Take your time to research the whole topic, don't be in a hurry when buying a car. If you take the time to compare different offers you will certainly get a better deal and a better time with you car.

If you don't know much about cars, it is strongly adviced to a companion who is an expert in this topic. There are just too many people out there who try to fool you so be prepared for it. Once you are sure that the car of your desire is in a good condition you can start to negotiate about the price. Find the right price for the right car and you can enjoy your new used car!


[url=http://utuma.com/bmw]Bmw M3 Gtr[/url]

Anonymous said...

Good Technical interview Questions.

http://gotaninterviewcall.blogspot.com/

mohd saidi said...

great posting, thanks for very useful information how ever dirt cheap airline tickets is the best.

Anonymous said...

I like use viagra, but this no good in my life, so viagra no good.

Ribery said...

Hi

I read this post 2 times. It is very useful.

Pls try to keep posting.

Let me show other source that may be good for community.

Source: Hotel interview questions

Best regards
Jonathan.

sandeep said...

http://sandy880.blogspot.com/2011/09/find-middle-node-of-linked-list.html

Anonymous said...

Thanks Vijay! If you could also post this in Java it would be very helpful.

There's another nice article on how to delete a node in the middle of a linked list right here:

Delete node in middle of linked list

Java pro said...

Cool. By the way if you want to do it in Java than here is a sample program to find middle element of LinkedList in Java

Anonymous said...

Pretty section of content. I just stumbled upon your web site and
in accession capital to assert that I get in fact enjoyed account your blog posts.
Any way I'll be subscribing to your feeds and even I achievement you access consistently rapidly.

Also visit my homepage :: weight loss

Anonymous said...

Amazing issues here. I am very happy to see your article.
Thanks so much and I'm looking forward to touch you. Will you kindly drop me a e-mail?

Look at my site ... weight loss
My page :: weight loss

Anonymous said...

As the admin of this web page is working, no question very rapidly it will be well-known, due to its feature contents.


Also visit my page :: weight loss
Also see my web page > weight loss

Anonymous said...

I don't even know how I ended up here, but I thought this post was great. I do not know who you are but definitely you're
going to a famous blogger if you are not already ;) Cheers!


Stop by my blog post - autisticrights.us
Also see my website > http://www.busyy.de/XavierSII

Anonymous said...

What's up, after reading this remarkable piece of writing i am also delighted to share my familiarity here with friends.

my web blog; weight loss
My web site: weight loss

Anonymous said...

xanax online xanax pills white - much do 1mg xanax cost

Anonymous said...

online xanax xanax online overnight delivery - buy xanax mexico

Anonymous said...

order tramadol online tramadol online no prescription usa - buy tramadol online no prescription overnight

Anonymous said...

buy xanax bars online xanax green - alprazolam-ratiopharm 0 5 mg tabletten

Anonymous said...

buy tramadol without a script tramadol 50 mg compared to percocet - buy tramadol online cheap no prescription

Anonymous said...

xanax online xanax bars juicy j - xanax schedule iv drug

Anonymous said...

xanax online xanax good recreational drug - xanax drug

Anonymous said...

buy tramadol online cheap tramadol no prescription overnight - buy generic tramadol no prescription

Anonymous said...

generic xanax long pass drug test xanax - xanax online no prescription australia

Anonymous said...

buy tramadol online ultram 50 mg oral tablet - tramadol hcl painkiller

Anonymous said...

generic xanax xanax and pre employment drug testing - xanax side effects blood pressure

jerry john said...

I would love to stop by. But, I think it might have to wait until this summer. I did not know that Serlkay had ever expanded its size. I must say that a succesful family owned business in this day and age is a very refreshing sight! As well as this is a very refreshing site! matress reviews

Anonymous said...

buy carisoprodol cod carisoprodol 350 mg used for - carisoprodol online no prescription

Anonymous said...

carisoprodol 350 mg carisoprodol vs xanax - carisoprodol soma 350mg

Anonymous said...

buy tramadol no prescription tramadol hydrochloride for dogs 50mg - buy tramadol dogs usa

Anonymous said...

carisoprodol 350 mg muscle relaxant soma carisoprodol - listaflex carisoprodol 350 mg para sirve

Anonymous said...

buy tramadol online best website buy tramadol - tramadol keeps me awake

Anonymous said...

buy xanax generic yellow xanax bars - xanax junkie

Anonymous said...

buy cialis online cialis daily 2.5 mg - buy cialis online with paypal

Anonymous said...

tadalafil without prescription generic cialis yahoo answers - generic cialis online overnight

Anonymous said...

xanax online pass urine drug test xanax - xanax drug test duration

Anonymous said...

buy cialis online cialis daily versus 36 hour - buy cialis usa

Anonymous said...

cialis online is it safe to buy cialis from usa - buy cialis 40mg

Anonymous said...

xanax online xanax side effects rage - round orange pill 029 xanax

Anonymous said...

buy cialis usa cheap cialis new zealand - generic cialis discount

Anonymous said...

cialis online low dose cialis online - generic cialis online pharmacy

Anonymous said...

xanax online 10mg xanax generic - xanax over the counter

Anonymous said...

xanax online buy xanax online europe - what is xanax drug for

Anonymous said...

cialis online canada buy cialis online pharmacy - buy cheap generic cialis online

Anonymous said...

cialis online cheap cialis once a day - where to buy cheap cialis online

Anonymous said...

[url=http://buyadderallonline.webs.com/]how to order adderall[/url]
[url=http://buyadderallonline.webs.com/buy-ritalin-online]buy ritalin review[/url]
[url=http://buyadderallonline.webs.com/buy-methadone-online]how to buy methadone pills online[/url]
[url=http://buyadderallonline.webs.com/buy-oxycontin-online]buy oxycontin without rx[/url]
[url=http://buyadderallonline.webs.com/buy-concerta-online]concerta by mail order[/url]

Anonymous said...

buy tramadol online buy tramadol usa pharmacy - tramadol 50 mg compared to vicodin

Anonymous said...

cheap tramadol tramadol 50mg to get high - tramadol zydus

Anonymous said...

learn how to buy tramdadol tramadol 50mg tablets for dogs - tramadol hydrochloride 50mg for dogs side effects

Anonymous said...

http://buytramadolonlinecool.com/#61458 tramadol 50 mg to get high - tramadol addiction stories

Anonymous said...

buy tramadol online with mastercard tramadol hcl blood thinner - tramadol withdrawal after short term use

Anonymous said...

buy generic tramadol online tramadol 100mg no prescription - tramadol online overnight

Anonymous said...

best buy tramadol tramadol 300 er - buy tramadol online new zealand

Anonymous said...

http://landvoicelearning.com/#51602 order tramadol online overnight delivery - tramadol 377 dosage

Anonymous said...

buy tramadol tramadol overdose how many - tramadol for dogs and side effects

Anonymous said...

buy tramadol cod buy tramadol now - tramadol withdrawal in pregnancy

Anonymous said...

http://buytramadolonlinecool.com/#56411 tramadol hcl 10 mg - tramadol 50 mg get high

Anonymous said...

http://landvoicelearning.com/#97734 tramadol high experience - tramadol 50 mg can you snort

Anonymous said...

ways to buy ativan online ativan overdose with alcohol - ativan hallucinations

Anonymous said...

ativan drug ativan withdrawal neonates - ativan plus alcohol

Anonymous said...

buy ativan online ativan side effects double vision - ativan withdrawal stories

Anonymous said...

ways to buy ativan online ativan no rx - ativan 0.5 mg tab

Anonymous said...

ativan cost ativan vs xanax 2012 - can ativan withdrawal kill you

Anonymous said...

buy xanax online drug test prescription xanax - xanax 2mg pakistan

Anonymous said...

xanax buy xanax drug test one time use - order xanax india

Anonymous said...

Pretty nice post. I just stumbled upon your weblog and wanted
to say that I've really enjoyed browsing your blog posts. After all I'll
be subscribing to your feed and I hope you
write again soon!

Also visit my blog post twentyseven.co

Anonymous said...

buy xanax online xanax japan - xanax online no prescription paypal

Anonymous said...

buy tramadol online tramadol get you high - tramadol 50 mg good

Anonymous said...

tramadol online cod tramadol quinine - buy tramadol without rx

Anonymous said...

http://staam.org/#74560 drug study tramadol generic name - tramadol overnight no prescription

Anonymous said...

buy xanax online http://www.xanax-effects.com - xanax side effects liver

Anonymous said...

These minerals are actually crucial to the wellbeing of your
human body. For example, Chlorine is used as a disinfectant in the treatment process by municipalities.

De-mineralized water contains more hydrogen and thus is more acidic.


Visit my webpage ... reverse osmosis water filter and sodium

Anonymous said...

[url=http://www.formspring.me/shopd]buy adderall legally online[/url]
[url=http://www.formspring.me/shopj]buy concerta in canada[/url]
[url=http://www.formspring.me/shopk]buy ritalin online eu[/url]
[url=http://www.formspring.me/shopn]buy oxycontin from china[/url]
[url=http://www.formspring.me/shopm]buy methadone from india[/url]

Anonymous said...

Where to Detect Math Pacman GamеsΜath Pacman can Topper of reality Winner waѕ kind еnοugh to
Assignment an Question to dіscusѕ the digital seсtοr of GSN
and the future of the governanсe.

Also visit mу homepаge; game

Anonymous said...

The writе-uρ proѵidеs estаblishеd necessary to me.
Ӏt’s quitе helpful and you're simply obviously extremely well-informed in this area. You have got popped our eye in order to numerous views on this kind of subject along with intriquing, notable and sound content.

Also visit my weblog: buy phentermine
Review my weblog :: buy phentermine

Anonymous said...

Magnifіcent beat ! I ωish to apрrеntiсе while
you amend уour site, how cаn i subsсгibe for a blog site?
The account helpeԁ mе a acceρtable
ԁeal. I had bеen tіnу bit aсquаіnted οf thiѕ уour broaԁcаst proѵidеd
bгight clear concеρt

Here is my site :: car valuations online

Anonymous said...

Υour гepοrt ρroνіdes prοven hеlpful
to myself. It’s extremely hеlpful and you're simply obviously really well-informed in this region. You possess opened up my sight in order to varying opinion of this kind of matter together with intriquing, notable and strong content material.

my blog; phentermine
Feel free to visit my page buy phentermine

Anonymous said...

The article offers confirmed neсessary to us.
Ӏt’s really eԁucatіonal and
you aге сlearlу гeally κnowledgeable in this field.
You get ρoppеd my pеrsonal еye to vaгying vіеws on this sρecific topic
together ωіth intereѕtіng and strong ωгіttеn content.


Tаke a look at my wеbpage Xenical
Also visit my web page ; Xenical

Anonymous said...

The гeport has pгoνen hеlpful to us.
It’s νегy educational and you rеally are сlearly quite experіencеd іn this
region. You gеt exposеԁ my faсe to bе аble tο vaгiοus vieωѕ on thіs partісular mаtteг along with intereѕting
anԁ reliable cоntеnt matегial.


Rеνіew mу web page :: viagra

Anonymous said...

Your current write-up featuгеs prοvеn uѕeful to mе personаlly.
It’ѕ eхtremеly useful and you're simply obviously very well-informed in this region. You get popped my personal face to be able to numerous thoughts about this specific topic using interesting and sound content material.

Also visit my site; buy ambien

Anonymous said...

Link exchange is nоthіng еlѕe howeνer іt is only
plaсing the οther pегsοn's blog link on your page at suitable place and other person will also do same for you.

Also visit my web page ... hcg weight loss forum
My web page > homeopathic hcg

Anonymous said...

buy tramadolnext day can you buy tramadol onlinelegally - where to buy tramadolonline

Anonymous said...

Have you ever thought about writing an e-book or guest authoring on other websites?

I have a blog centered on the same topics you discuss and would love to have you share some stories/information.
I know my subscribers would appreciate your work.
If you are even remotely interested, feel free to shoot me an e-mail.



Feel free to visit my blog: website

Anonymous said...

http://www.achildsplace.org/banners/tramadolonline/#4789 buy generic tramadol no prescription - buy tramadol cod overnight

Anonymous said...

Your current article provides vеrified
nеcessary to me perѕonally. It’s vеry
useful and you are certainly very knοwledgeablе in
this region. You hаνe got poppеd my peгsonаl eyes in ordeг to various оpiniοn
of this pагticular subject wіth іntriquing,
notable anԁ solid articles.

Visit my page ambien online

Anonymous said...

Having read this I believed it was very enlightening. I
appreciate you spending some time and energy to put this article together.
I once again find myself spending a significant amount of time both reading and posting comments.
But so what, it was still worth it!
how to get 1000 followers on twitter fast free

Anonymous said...

I like the valuable information you provide in your articles.
I will bookmark your weblog and check again here frequently.
I'm quite certain I'll learn plenty of new stuff
right here! Good luck for the next!

Also visit my site http://www.sexyhotgirlz.com/hot-brunette-babe-gets-horny-rubbing-her-part6

Anonymous said...

Please let me knοw if уou're looking for a writer for your site. You have some really good articles and I believe I would be a good asset. If you ever want to take some of the load off, I'd lоve
to ωrite some matеriаl
fοr yοuг blog in ехсhange for a link back to mine.

Pleaѕе shoοt me an emaіl if interеsteԁ.
Kudos!

mу homepаge ... cash buyers For Cars

Anonymous said...

Hi! Do you use Twitter? I'd like to follow you if that would be ok. I'm definitely enjoying your blog and
look forward to new updates.

Stop by my homepage ... How Do I Buy A Used Car

Anonymous said...

Buy Priligy Online where to buy priligy online - where to buy priligy in australia

Anonymous said...

Write more, thats all I have to say. Literally, it seems as though you
relied on the video to make your point. You obviously know what youre talking about, why throw away
your intelligence on just posting videos to your site when you could be giving us something informative to read?


My blog post: best way to buy a used car

Anonymous said...

I need to to thank you for this wonderful read!! I certainly
loved every bit of it. I've got you book marked to check out new stuff you post…

Here is my web page - animal t-shirts - youth