Tell me more ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 9 down vote favorite
3

I implemented reversing a linked list in iterative way, just by knowing we need 3 pointers and I have never seen a code before, when I coded. I ran this code and tested it, it works fine. Even for null element and one element. But all the implementations on net have slightly different code. I was just wondering, how my algorithm is.

Do you guys see any major concern in my implementation?

int reverse(List *l) {

 if(!l) {
        printf("List is NULL \n");
        return -1;
 }

 if(!l->head) {
        printf("List is empty \n");
        return -1;
 }

 Node *prev_node = l->head;
 Node *curr_node = l->head->next;

 while(curr_node) {
        prev_node->next = curr_node->next;
        curr_node->next = l->head;
        l->head = curr_node;
        curr_node = prev_node->next;
 }

 return 0;
}
share|improve this question

3 Answers

up vote 5 down vote

Try this code, it's a bit easier to follow. Also, you define the return type as int, but you're not returning anything meaningful, so you should change the function to void.

void reverse(Node* & node)
{
    if(!node)
    {
        cerr << "The node doesn't exist \n" << endl;
        return;
    }

    Node* curr;
    Node* prev = NULL;

    while(node != NULL)
    {
        curr = node->next;
        node->next = prev;
        prev = node;
        node = curr;
    }
}
share|improve this answer
2  
You needn't to check node in the if block, since you did it in the while loop. – zdd Oct 20 '12 at 7:19
1  
Good call. The error message is unnecessary I'd say. – dmastylo Oct 20 '12 at 8:43
1  
This code doesn't work. The node pointer is passed by value so the caller's copy of the pointer is unchanged. The typical solution is to return the new head value (see zdd's answer). – Blastfurnace Oct 20 '12 at 16:03
Yeah that was my bad, forgot to add the by ref. – dmastylo Oct 20 '12 at 19:31
up vote 6 down vote

If you don't care about the origin list, we can use the head of it as the iterator, You should return the new head after reverse, or the new list will lost. enter image description here

#include <stdio.h>

struct Node
{
    int data;
    Node* next;
    Node(int value, Node* ptr):data(value), next(ptr){} 
};

// Reverse list and return the new head
Node* reverse_list(Node* head)
{
    Node* p = NULL;
    Node* q = head;
    while(q)
    {
        Node* t = q->next;
        q->next = p;
        p = q;
        q = t;
    }

    return p; // new head
}

void print_list(Node* head)
{
    Node* t = head;
    while(t)
    {
        printf("%d\n", t->data);
        t = t->next;
    }
}

void main()
{
    Node* head = new Node(1, NULL);
    Node* p = head;
    for(int i = 2; i < 10; ++i)
    {
        p->next = new Node(i, NULL);
        p = p->next;
    }
    print_list(head);

    Node* newHead = reverse_list(head);
    print_list(newHead);

    getchar();
}
share|improve this answer
up vote 2 down vote

I would suggest changing the return type to a pointer to the list, and drop all of your error messages -- they aren't relevant. If passed in null, return null.

In general you should seperate your logic from your UI as much as possible -- and this function needs no UI. Even if you consider this a form of error/exception handling, you should not be doing it in this case as there's no reason to allow this code to fail -- you are not allocating new memory, the only thing that can go wrong is not enough stack space, which happens before your code runs.

Elsewhere you may care about whether the list is empty or the pointer to the list is null, but not in the code to reverse the list -- it should be foolproof.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.