Velocity Reviews

Velocity Reviews (http://www.velocityreviews.com/forums/index.php)
-   C Programming (http://www.velocityreviews.com/forums/f42-c-programming.html)
-   -   Linked list need help... (http://www.velocityreviews.com/forums/t439719-linked-list-need-help.html)

XXXXXX.working.in.my.blood 10-08-2005 05:08 PM

Linked list need help...
 
hi all,
i need help with linked lists...
the problem is this, "reverse the contents of a singly linked list
without using a temporary node"...
solution with code will be appreciated...


Skarmander 10-08-2005 05:09 PM

Re: Linked list need help...
 
XXXXXX.working.in.my.blood wrote:
> hi all,
> i need help with linked lists...
> the problem is this, "reverse the contents of a singly linked list
> without using a temporary node"...
> solution with code will be appreciated...
>

It's not going to happen. We don't do homework assignments, sorry.

You're free to ask specific questions on a solution you've come up with
and can't seem to complete, and we'll be happy to answer any language
questions you might have.

But do your own homework first.

Oh, and if you're that hell-bent on getting the quick and easy solutions
without understanding: consider using Google. This problem is very old.

S.

XXXXXX.working.in.my.blood 10-08-2005 05:14 PM

Re: Linked list need help...
 
i don want to be rude but i was asked this question by one of the HRs
in an interview. i couldn't answer the question, i dont admit that i
coudn't get the job coz' i didn't answer this but just want to know,
if u don have an answer just leave it, and i am not asking anyone to do
homework assignments its just a request.
thank you very much for the help
....


pete 10-08-2005 05:34 PM

Re: Linked list need help...
 
XXXXXX.working.in.my.blood wrote:
>
> hi all,
> i need help with linked lists...
> the problem is this, "reverse the contents of a singly linked list
> without using a temporary node"...
> solution with code will be appreciated...


I can't imagine how a temporary node would be helpful.

/* BEGIN list.h */

#ifndef H_LIST
#define H_LIST

typedef struct list_node {
struct list_node *next;
void *data;
} list_type;

list_type *list_make(long unsigned);
list_type *list_rev(list_type *);
list_type *list_sort(list_type *,
int (*)(const list_type *, const list_type *));
void list_free(list_type *, void (*)(void *));

#endif

/* END list.h */

/* BEGIN list.c */

#include <stdlib.h>

#include "list.h"

static long unsigned list_count(list_type *);
static list_type *node_sort(list_type *, long unsigned,
int (*)(const list_type *, const list_type *));
static list_type *list_merge(list_type *, list_type *,
int (*)(const list_type *, const list_type *));
static list_type *list_split(list_type *, long unsigned);

list_type *list_rev(list_type *head)
{
list_type *next_node, *previous;

if (head != NULL) {
next_node = head -> next;
head -> next = NULL;
while (next_node != NULL) {
previous = next_node -> next;
next_node -> next = head;
head = next_node;
next_node = previous;
}
}
return head;
}

list_type *list_make(long unsigned count)
{
list_type *node, *list;

list = count != 0 ? malloc(sizeof *list) : NULL;
if (list != NULL) {
node = list;
while (--count != 0) {
node -> data = NULL;
node -> next = malloc(sizeof *node -> next);
if (node -> next == NULL) {
list_free(list, free);
return NULL;
} else {
node = node -> next;
}
}
node -> data = NULL;
node -> next = NULL;
}
return list;
}

void list_free(list_type *node, void (*free_data)(void *))
{
list_type *next_node;

while (node != NULL) {
next_node = node -> next;
free_data(node -> data);
free(node);
node = next_node;
}
}

list_type *list_sort(list_type *head,
int (*compar)(const list_type *, const list_type *))
{
return node_sort(head, list_count(head), compar);
}

static long unsigned list_count(list_type *head)
{
long unsigned count;

for (count = 0; head != NULL; head = head -> next) {
++count;
}
return count;
}

static list_type *node_sort(list_type *head, long unsigned count,
int (*compar)(const list_type *, const list_type *))
{
long unsigned half;
list_type *tail;

if (count > 1) {
half = count / 2;
tail = list_split(head, half);
tail = node_sort(tail, count - half, compar);
head = node_sort(head, half, compar);
head = list_merge(head, tail, compar);
}
return head;
}

static list_type *list_split(list_type *head, long unsigned count)
{
list_type *tail;

while (count-- > 1) {
head = head -> next;
}
tail = head -> next;
head -> next = NULL;
return tail;
}

static list_type *list_merge(list_type *head, list_type *tail,
int (*compar)(const list_type *, const list_type *))
{
list_type *list, *sorted, **node;

node = compar(head, tail) > 0 ? &tail : &head;
sorted = list = *node;
*node = sorted -> next;
while (*node != NULL) {
node = compar(head, tail) > 0 ? &tail : &head;
sorted -> next = *node;
sorted = *node;
*node = sorted -> next;
}
sorted -> next = head != NULL ? head : tail;
return list;
}

/* END list.c */

/* BEGIN list_sort.c */

#include <stdio.h>
#include <stdlib.h>

#include "list.h"

#define NODES 17
#define LU_RAND_SEED 123456789LU
#define LU_RAND(S) ((S) * 69069 + 362437 & 0xffffffff)

struct score {
float literature;
float history;
float sociology;
};

int hist_score_comp(const list_type *, const list_type *);
void score_init(list_type *, long unsigned);
void score_print(list_type *);

int main(void)
{
list_type *score;

score = list_make(NODES);
if (score == NULL) {
fputs("The score list was not allocated.\n", stderr);
exit(EXIT_FAILURE);
}
score_init(score, LU_RAND_SEED);
puts("BEGIN output from list_sort.c\n\nRandom order");
score_print(score);
puts("Sorted on history");
score = list_sort(score, hist_score_comp);
score_print(score);
puts("Reverse Sorted order");
score = list_rev(score);
score_print(score);
puts("END output from list_sort.c\n");
list_free(score, free);
return 0;
}

void score_init(list_type *node, long unsigned seed)
{
while (node != NULL) {
node -> data = malloc(sizeof (struct score));
if (node -> data == NULL) {
fputs("malloc problem\n", stderr);
exit(EXIT_FAILURE);
}
seed = LU_RAND(seed);
((struct score *)node -> data) -> literature
= seed % 40 + 60.0f;
seed = LU_RAND(seed);
((struct score *)node -> data) -> history
= seed % 40 + 60.0f;
seed = LU_RAND(seed);
((struct score *)node -> data) -> sociology
= seed % 40 + 60.0f;
node = node -> next;
}
}

void score_print(list_type *node)
{
float score;

while (node != NULL) {
score = ((struct score *)node -> data) -> literature;
printf("literature %d ", (int)score);
score = ((struct score *)node -> data) -> history;
printf("history %d ", (int)score);
score = ((struct score *)node -> data) -> sociology;
printf("sociology %d\n", (int)score);
node = node -> next;
}
putchar('\n');
}

int hist_score_comp(const list_type *head, const list_type *tail)
{
float first = ((struct score *)head -> data) -> history;
float second = ((struct score *)tail -> data) -> history;

return second > first ? -1 : second != first;
}

/* END list_sort.c */


--
pete

Alexei A. Frounze 10-08-2005 06:43 PM

Re: Linked list need help...
 
"XXXXXX.working.in.my.blood" <bharath144@gmail.com> wrote in message
news:1128791645.979839.200110@g44g2000cwa.googlegr oups.com...
> i don want to be rude


Then don't :)

> but i was asked this question by one of the HRs
> in an interview.


That's fine. But we're not preparing or training for interviews in this
group, we're to help with standard C here, which, believe or not, has
vanishingly little to do with this your problem of singly-linked list
reversal. What you want is an algorithm. And its implementation (please note
that implementation != algorithm) could be done in Pascal or any other
language supporting pointers/references/links/whatever. So, why this group?

> i couldn't answer the question, i dont admit that i
> coudn't get the job coz' i didn't answer this but just want to know,

....

On that matter, I'd consider preparing for the interview longer and better.
There're lots of typical interview questions for programmers on the net. Try
finding and solving those that are told to be asked at microsoft. I found
those (about 100) and had a like a month of fun solving them (no I wasn't
solving them from 9am to 6pm, I had other things to do, my job, that's why
it wasn't quick). And there were questions going far beyond simple list
reversal. If it's (still) important to you, do the same. At least give it a
good try, crack your brains solving them. And it's best if you do it w/o
external help -- that's how you can make your head work and see what you
can.

Alex



Dale 10-08-2005 07:33 PM

Re: Linked list need help...
 
"XXXXXX.working.in.my.blood" <bharath144@gmail.com> wrote in
news:1128791289.259482.105340@o13g2000cwo.googlegr oups.com:
>
> hi all,
> i need help with linked lists...
> the problem is this, "reverse the contents of a singly linked list
> without using a temporary node"...


Why would you need a temp node? Just reverse all the pointers.

> solution with code will be appreciated...


Solution above; code denied.

__frank__ 10-09-2005 08:28 AM

Re: Linked list need help...
 
pete ha scritto:

> #ifndef H_LIST
> #define H_LIST


Why the above directives?
Thanks

Mabden 10-09-2005 10:32 AM

Re: Linked list need help...
 
"Alexei A. Frounze" <alexfru@chat.ru> wrote in message
news:3qqiajFft79pU1@individual.net...
> "XXXXXX.working.in.my.blood" <bharath144@gmail.com> wrote in message
> news:1128791645.979839.200110@g44g2000cwa.googlegr oups.com...
> > but i was asked this question by one of the HRs
> > in an interview.

>
> That's fine. But we're not preparing or training for interviews in

this
> group, we're to help with standard C here, which, believe or not, has
> vanishingly little to do with this your problem of singly-linked list
> reversal. What you want is an algorithm. And its implementation

(please note
> that implementation != algorithm) could be done in Pascal or any other
> language supporting pointers/references/links/whatever. So, why this

group?

The ad I saw said said don't submit a resume unless you could solve the
problem in 20 minutes in any language. I wrote up a C version in about
25 while watching TV (ie: during commercials). It certainly seemed like
homework, since the constraint of a singly-linked list that you want to
transverse two ways is very artificial. I almost wrote a nasty email to
the firm, but I am much too shy and subtle...

> > i couldn't answer the question, i dont admit that i
> > coudn't get the job coz' i didn't answer this but just want to

know,

It's not difficult, but once reversed, you lose the forward reference -
you'd have to re-reverse it to get back to the original list. It takes
N+(N-1)+(N-2) ... + 1 operations in my algorithm. Of course, you could
just set up a second list that was doubly-linked and would be just
pointers to the old list. That would take one pass, well two if you then
update the original list. Damn I should have thought of that before!
Hey! Can I have my interview back...?! :-0

> On that matter, I'd consider preparing for the interview longer and

better.
> There're lots of typical interview questions for programmers on the

net. Try
> finding and solving those that are told to be asked at microsoft. I

found
> those (about 100) and had a like a month of fun solving them (no I

wasn't
> solving them from 9am to 6pm, I had other things to do, my job, that's

why
> it wasn't quick). And there were questions going far beyond simple

list
> reversal. If it's (still) important to you, do the same. At least give

it a
> good try, crack your brains solving them. And it's best if you do it

w/o
> external help -- that's how you can make your head work and see what

you
> can.


"see what you can." Can WHAT?!!

--
Mabden



delahaye.emmanuel 10-09-2005 10:46 AM

Re: Linked list need help...
 
__frank__ a écrit :
> pete ha scritto:
>
>> #ifndef H_LIST
>> #define H_LIST


> Why the above directives?


It's a guard against multiple inclusions.

When you write a lbrary, you can't know in advance how will the headers
be included by the users. This guard prevents against multiple
inclusions into a same compile unit.

Sandeep 10-09-2005 01:46 PM

Re: Linked list need help...
 
the problem is this, "reverse the contents of a singly linked list
without using a temporary node"...

You can use two temp pointers ( note that it is not a temporary node)
and rearrange all the pointers .... Try to figure out the algorithm ...



All times are GMT. The time now is 08:10 AM.

Powered by vBulletin®. Copyright ©2000 - 2014, vBulletin Solutions, Inc.
SEO by vBSEO ©2010, Crawlability, Inc.