Skip to content

Instantly share code, notes, and snippets.

@cslarsen

cslarsen/revlink.c

Created June 30, 2010 00:39
Show Gist options
  • Save cslarsen/458048 to your computer and use it in GitHub Desktop.
Save cslarsen/458048 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. cslarsen renamed this gist Jun 30, 2010. 1 changed file with 0 additions and 0 deletions.
    0 gistfile1.h → revlink.c
    View file
    File renamed without changes.
  2. cslarsen renamed this gist Jun 30, 2010. 1 changed file with 4 additions and 0 deletions.
    4 changes: 4 additions & 0 deletions gistfile1.txt → gistfile1.h
    View file
    Original file line number Diff line number Diff line change
    @@ -1,5 +1,9 @@
    /*
    * Reverse singly linked list. (C)
    *
    * Written in a hurry after reading this HN thread:
    * http://news.ycombinator.com/item?id=1471988
    *
    */

    #include <stdio.h>
  3. cslarsen revised this gist Jun 30, 2010. 1 changed file with 1 addition and 1 deletion.
    2 changes: 1 addition & 1 deletion gistfile1.txt
    View file
    Original file line number Diff line number Diff line change
    @@ -1,5 +1,5 @@
    /*
    * Reverse singly linked list.
    * Reverse singly linked list. (C)
    */

    #include <stdio.h>
  4. cslarsen created this gist Jun 30, 2010.
    83 changes: 83 additions & 0 deletions gistfile1.txt
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,83 @@
    /*
    * Reverse singly linked list.
    */

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

    struct item {
    const char* msg;
    struct item* next;
    };

    struct item* new(const char* msg)
    {
    struct item* p = (struct item*) malloc(sizeof(struct item));
    p->next = NULL;
    p->msg = msg;
    return p;
    }

    struct item* append(struct item *p, struct item *next)
    {
    p->next = next;
    next->next = NULL;
    return next;
    }

    void traverse(struct item* p, void (*func)(struct item*))
    {
    while ( p != NULL ) {
    struct item* next = p->next;
    func(p);
    p = next;
    }
    }

    void print_info(struct item* p)
    {
    printf("0x%lx: '%s'\n", (long unsigned int) p, p->msg);
    }

    void free_struct(struct item* p)
    {
    free(p);
    }

    struct item* reverse(struct item* p)
    {
    struct item *root = p, *prev = NULL, *next;

    while ( p != NULL ) {
    next = p->next;
    p->next = prev;
    prev = p;
    p = next;
    }

    root->next = NULL;
    return prev;
    }

    int main(int argc, char** argv)
    {
    struct item *p = new("one");
    struct item *root = p;

    p = append(p, new("two"));
    p = append(p, new("three"));
    p = append(p, new("four"));
    p = append(p, new("five"));
    p = append(p, new("six"));

    printf("Normal list:\n");
    traverse(root, print_info);

    printf("Reversed list:\n");
    root = reverse(root);
    traverse(root, print_info);

    // no need for this, strictly speaking:
    traverse(root, free_struct);
    return 0;
    }