Linked list need help...

Discussion in 'C Programming' started by XXXXXX.working.in.my.blood, Oct 8, 2005.

  1. 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...
    XXXXXX.working.in.my.blood, Oct 8, 2005
    #1
    1. Advertising

  2. XXXXXX.working.in.my.blood

    Skarmander Guest

    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.
    Skarmander, Oct 8, 2005
    #2
    1. Advertising

  3. 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
    ....
    XXXXXX.working.in.my.blood, Oct 8, 2005
    #3
  4. XXXXXX.working.in.my.blood

    pete Guest

    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
    pete, Oct 8, 2005
    #4
  5. "XXXXXX.working.in.my.blood" <> wrote in message
    news:...
    > 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
    Alexei A. Frounze, Oct 8, 2005
    #5
  6. XXXXXX.working.in.my.blood

    Dale Guest

    "XXXXXX.working.in.my.blood" <> wrote in
    news::
    >
    > 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.
    Dale, Oct 8, 2005
    #6
  7. XXXXXX.working.in.my.blood

    __frank__ Guest

    pete ha scritto:

    > #ifndef H_LIST
    > #define H_LIST


    Why the above directives?
    Thanks
    __frank__, Oct 9, 2005
    #7
  8. XXXXXX.working.in.my.blood

    Mabden Guest

    "Alexei A. Frounze" <> wrote in message
    news:...
    > "XXXXXX.working.in.my.blood" <> wrote in message
    > news:...
    > > 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
    Mabden, Oct 9, 2005
    #8
  9. __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.
    delahaye.emmanuel, Oct 9, 2005
    #9
  10. XXXXXX.working.in.my.blood

    Sandeep Guest

    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 ...
    Sandeep, Oct 9, 2005
    #10
  11. XXXXXX.working.in.my.blood

    pete Guest

    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
    pete, Oct 9, 2005
    #11
  12. "Mabden" <mabden@sbc_global.net> wrote in message
    news:gl62f.10$...
    > "Alexei A. Frounze" <> 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
    Alexei A. Frounze, Oct 9, 2005
    #12
  13. XXXXXX.working.in.my.blood

    Alan Balmer Guest

    On 8 Oct 2005 10:08:09 -0700, "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"...


    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
    Alan Balmer, Oct 10, 2005
    #13
  14. XXXXXX.working.in.my.blood

    Jaspreet Guest

    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.
    Jaspreet, Oct 10, 2005
    #14
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Chris Ritchey
    Replies:
    7
    Views:
    458
    emerth
    Jul 10, 2003
  2. Chris Ritchey

    Generating a char* from a linked list of linked lists

    Chris Ritchey, Jul 9, 2003, in forum: C Programming
    Replies:
    7
    Views:
    447
    emerth
    Jul 10, 2003
  3. fool
    Replies:
    14
    Views:
    483
    Barry Schwarz
    Jul 3, 2006
  4. joshd
    Replies:
    12
    Views:
    650
    John Carson
    Oct 2, 2006
  5. jawdoc
    Replies:
    9
    Views:
    728
    Chris Thomasson
    Mar 10, 2008
Loading...

Share This Page