467,135 Members | 1,214 Online
Bytes | Developer Community
Ask Question

Home New Posts Topics Members FAQ

Post your question to a community of 467,135 developers. It's quick & easy.

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

Nov 15 '05 #1
  • viewed: 1791
Share:
13 Replies
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.
Nov 15 '05 #2
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
....

Nov 15 '05 #3
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
Nov 15 '05 #4
"XXXXXX.working.in.my.blood" <bh********@gmail.com> wrote in message
news:11**********************@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
Nov 15 '05 #5
"XXXXXX.working.in.my.blood" <bh********@gmail.com> wrote in
news:11**********************@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.
Nov 15 '05 #6
pete ha scritto:
#ifndef H_LIST
#define H_LIST


Why the above directives?
Thanks
Nov 15 '05 #7
"Alexei A. Frounze" <al*****@chat.ru> wrote in message
news:3q************@individual.net...
"XXXXXX.working.in.my.blood" <bh********@gmail.com> wrote in message
news:11**********************@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
Nov 15 '05 #8
__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.
Nov 15 '05 #9
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 ...

Nov 15 '05 #10
delahaye.emmanuel wrote:

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


The spelling of "__frank__", combined with his question,
causes me to wonder if __frank__ is reading system headers
to find examples of good code.

So, I will advise that
identifiers in system headers
use reserved naming conventions,
such as two leading __underscores,
with the implication being that
the programmer can and should avoid naming conflicts
by not using identifiers begining with two uderscores.

The rules for when you should and shouldn't begin
identifiers with _underscores are complicated enough,
so that when writing C code, it's simplest to remember
just not to begin any identifiers with any underscores.

--
pete
Nov 15 '05 #11
"Mabden" <mabden@sbc_global.net> wrote in message
news:gl************@newssvr13.news.prodigy.com...
"Alexei A. Frounze" <al*****@chat.ru> wrote in message

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


What you can *do*. It often happens that you don't know what you can do and
what you can't until you try doing it. Sometimes you think the problem is
simple but when you start working on it, you change the opinion. The
opposite is also possible. Attempting to solve problems tells you what and
how you can do and tells you what you should do about the things that you
can't...

Alex
Nov 15 '05 #12
On 8 Oct 2005 10:08:09 -0700, "XXXXXX.working.in.my.blood"
<bh********@gmail.com> 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"...
Why would you want to do that?
solution with code will be appreciated...


Give us the email address of your teacher and we'll send it direct.
--
Al Balmer
Balmer Consulting
re************************@att.net
Nov 15 '05 #13

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


Hi

Proper English please. Try to make the 1st character of a sentence in
capitals. Get your keyboard repaired. There seems to be something wrong
with the dot ('.') key. It alwyas seems to get pressed thrice.

As for coming to the problem, try and solve it yourself. Please show us
what you attempted and then one of the members would be able to help
you further.

Thanks and have a wonderfuld day.

Nov 15 '05 #14

This discussion thread is closed

Replies have been disabled for this discussion.

Similar topics

7 posts views Thread by Chris Ritchey | last post: by
5 posts views Thread by Darryl B | last post: by
8 posts views Thread by simpleman | last post: by
5 posts views Thread by John N. | last post: by
1 post views Thread by Little | last post: by
12 posts views Thread by joshd | last post: by
2 posts views Thread by phiefer3 | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.