Reversing a linked list

Question

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;
}

Answer 1

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.

#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();
}

Answer 2

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;
    }
}

Answer 3

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.