Unable to reverse a linked list

Question

I was trying to reverse a linked list, however whenever I execute the following function, I get only the last element. For example, if the list contained 11,12,13 earlier. After executing the function, it contains only 13. Kindly point out the bug in my code

void reverselist() {
    struct node *a, *b, *c;
    a = NULL;
    b = c = start;

    while (c != NULL) {
        c = b->next;
        b->next = a;
        a = b;
        b = c;
    }
    start = c;
}

score 1 · Answer 1 · answered Jul 17 '12 at 11:30

1

Doesn't your loop guard insure that start is null?
If you aren't using start to identify the first element of the list, then the variable you ARE using is still pointing to what WAS the first element, which is now the last.

answered Jul 17 '12 at 11:30

Scott Hunter

48,888
12
60
101

martiert · Answer 2 · 2012-07-17T12:34:32.163

0

I would have made a prepend function, and done the following:

struct node* prepend(struct node* root, int value)
{
    struct node* new_root = malloc(sizeof(struct node));
    new_root->next = root;
    return new_root;
}

struct node* reverselist(struct node* inlist)
{
    struct node* outlist = NULL;

    while(inlist != NULL) {
        struct node* new_root = prepend(outlist, inlist->value);
        outlist = new_root;
        inlist = inlist->next;
    }

    return outlist;
}

Have not tested this, but guess you grasp the idea of it. Might be just your variable names, which don't describe anything, but I think this approach is cleaner, and easier to understand what actually happens.

EDIT:

Got a question why I don't do it inplace, so I'll answer it here:

Can you do it inplace? Are you sure you don't wish to keep the original list?
Do you need to do it inplace? Is the malloc to time consuming/is this a performance critical part of your code? Remember: premature optimization is the root of all evil.

Thing is, this is a first implementation. It should work, and not be optimized. It should also have a test written before this implementation is even thought of, and you should keep this slow, un-optimized implementation until the test passes, and you have proved that it's to slow for your use!

When you have a passing unit test, and proven the implementation to be to slow, you should optimize the code, and make sure it still passes the test, without changing the test.

Also, is it necessary inplace operations which is the answer? What about allocating the memory before reverting it, this way you only have one allocation call, and should hopefully get a nice performance boost.

This way everyone is happy, you have a cleaner code and avoid the risk of having Uncle Bob showing up at your door with a shotgun.

edited Jul 17 '12 at 12:34

answered Jul 17 '12 at 11:41

martiert

741
4
13

Why allocate memory when you can do it in-place with a loop? – JimR Jul 17 '12 at 11:54
Well, if your list has addAtTail/addAtHead type calls, reading one list backwards, adding to a new list forwards and delete() the old list is, well, just easier than thinking about mutilating the existing list with its 0/1 entry corner cases etc. It is lazy and inefficient, yes, but I confess to doing it in those cases where the operation is infrequent and time is not of the essence :) – Martin James Jul 17 '12 at 12:07
@MartinJames: Write it once and stick it in a snippets file? :) – JimR Jul 17 '12 at 12:13
@JimR: Tried to answer your question in an edit. Martin James: I don't see any reason to "confess" that you do it, as I much prefer this to an inline implementation, which gets quite ugly. Code quality is, in my eyes, always preferable to performance, if performance is not essential for that particular code. – martiert Jul 17 '12 at 12:39
@martiert: I see adding allocation to something that doesn't truly need it as a quality problem. More places to fail. It has nothing to do with performance. – JimR Jul 17 '12 at 19:55
@JimR, seems like that's might be where we differ in opinion then. In modern computers, and many embedded devices as well, there is no lack of memory, so being careful about the memory makes no sense. Of course, if this is a huge chunk of memory, and you really can't allocate, that's a different story. Any way, avoiding the allocations is also a type of optimization, optimizing for minimal memory usage, and should still be done after you have made a passing test. I also find that self explanatory code to generally give higher quality than the hassle it might be to avoid an allocation. – martiert Jul 18 '12 at 07:35

score 0 · Answer 3 · answered Jul 17 '12 at 12:01


// You should assume that Node has a Node* called next that
// points to the next item in a list
// Returns the head of the reversed list if successful, else NULL / 0
Node *reverse( Node *head )
{
    Node *prev = NULL;

    while( head != NULL )
    {
        // Save next since we will destroy it
        Node *next = head->next;

        // next and previous are now reversed
        head->next = prev;

        // Advance through the list
        prev = head;
        head = next;
    }
    return previous;
}

score 0 · Accepted Answer · answered Jul 17 '12 at 14:24

0

c is a helper pointer.

void reverselist()
{
    struct node *a, *b, *c;
    a=NULL;
    b=start;
    while(b!=NULL)
    {
        c=b->next
        b->next=a;
        a=b
        b=c
    }
    start=a;
}

answered Jul 17 '12 at 14:24

Avi Cohen

3,102
2
25
26

Unable to reverse a linked list

4 Answers4

Linked

Related