News for hackers. Stuff that matters.
Re:Job Interview question: "Reverse a Linked-list. Write cod... by mbrubeck on Monday January 18, 2010 @11:48AM (#1060188)
How does one manage to publish code that is so badly botched? [Update: The code in the blog post is fixed; the original versions are below.]

The recursive solution does not work. It never sets “next” to NULL for the original head of the list, so now the list ends with a cycle.

The non-recursive solution does not work either. It never assigns anything to “previous”, so it always returns NULL and sets all of the “next” pointers to NULL.

This is easy to see if you actually compile and run both of these on some sample input:

    #include <stdio.h>
    
    typedef struct Node {
        struct Node *next;
        int value;
    } Node;
    
    Node * reverse( Node * ptr )
    {
        Node * temp;
        if(ptr->next == NULL) {
            return ptr;
        } else {
            temp = reverse(ptr->next);
            ptr->next->next = ptr;
            return temp;
        }
    }
    
    Node * ireverse( Node * ptr )
    {
        Node * temp;
        Node * previous = NULL;
        while(ptr != NULL) {
            temp = ptr->next;
            ptr->next = previous;
            ptr = temp;
        }
        return previous;
    }
    
    void print(Node *head) {
        Node *curr;
        for (curr = head; curr != NULL; curr = curr->next) {
            printf("%d\n", curr->value);
        }
    }
    
    main() {
        Node a, b, c;
        a.value = 1;
        a.next = &b;
        b.value = 2;
        b.next = &c;
        c.value = 3;
        c.next = NULL;
        printf("Iterative:\n")
        print(ireverse(&a));
    
        a.value = 1;
        a.next = &b;
        b.value = 2;
        b.next = &c;
        c.value = 3;
        c.next = NULL;
        printf("Recursive:\n")
        print(reverse(&a));
    }
Re:Job Interview question: "Reverse a Linked-list. Write cod... by Monkeyget on Monday January 18, 2010 @12:32PM (#1060327)
Your comment reminds me of the experience Leslie Lamport performed : checking the ten first quick sort algorithms found with a search engine and how half of them were wrong.
Re:Job Interview question: "Reverse a Linked-list. Write cod... by mjterave on Monday January 18, 2010 @12:06PM (#1060245)
> How does one manage to publish code that is so badly botched?

It's just a blog. There's effectively no barrier to entry. :)

Re:Job Interview question: "Reverse a Linked-list. Write cod... by viraptor on Monday January 18, 2010 @12:19PM (#1060296)
That's why TDB (T.D.Blogging) was invented. First you write a specification of your new post, then hire a blog reader to prepare tests for your future content and... oh wait...
Re:Job Interview question: "Reverse a Linked-list. Write cod... by tybris on Monday January 18, 2010 @12:13PM (#1060278)
That's why we have peer review (you).
Re:Job Interview question: "Reverse a Linked-list. Write cod... by mbrubeck on Monday January 18, 2010 @12:18PM (#1060288)
Peer review is a pretty heavy-weight solution when just compiling and running the code would tell you it's broken.