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).

64 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...

[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/

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.

Admin 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...

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

Unknown 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 tramadol no prescription tramadol hydrochloride for dogs 50mg - buy tramadol dogs usa

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...

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

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...

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...

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

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...

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...

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...

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...

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...

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 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

Shivam Kumar said...

Nice article well explained . there is good linkedlist examples collection
visit Java Linked list examples

James said...

Once you have purchased your mattress, maintenance is important to make your mattress last as long as specified by the manufacturers guarantee. truck mattress