Reversing a linked list by iteration and recursion

Question

From my original question on Stack Overflow: Is my implementation of reversing a linked list correct?

I'm a beginner at C and I'd like to know about style, and correctness of the reverse algorithms. What about memory management?

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

typedef struct Node {
    int val;
    struct Node *next;
} Node;


Node * build_list(int num);
Node * reverse_list(Node * head);
static Node * r_reverseItem(Node * last, Node * head);
Node * r_reverse(Node * head);

/*
 * Function which iterates to 100 creating nodes
 * and linking them to head
 *
 */
Node * build_list(int num) {

    Node * head = NULL;
    Node * curr;

    int i;
    for(i=0;i<num;i++) {
    curr = (Node *)malloc(sizeof(Node));
    curr->val = i;
    curr->next = head;
    head = curr;
    }
    return head;
}

/*
 * Function which reverses linked list 
 * by traversing list and flipping ptr of curr to last
 * @param head
 *
 */
Node * reverse_list(Node * head) {

    if (head == NULL) //only one elem
    return NULL;

    Node * last = NULL;
    do {
    Node * next = head->next;
    head->next = last;
    last = head;
    head = next;
    }
    while (head != NULL);
    return last;
}

/*
 * Function which recursively reverses linked list
 * @param last
 * @param head
 *
 */
static Node * r_reverseItem(Node * last, Node * head) {

    if (head == NULL) 
    return last;

    Node * next = head->next;
    head->next = last;
    return r_reverseItem(head,next);
}

Node * r_reverse(Node * head) {
    return r_reverseItem(NULL, head);
}


int main (void) {
    Node * head = build_list(5);
    Node * curr;
    head = r_reverse(head);
    //    head = reverse_list(head);
    while(head) {
      printf("%d\n",head->val);
      curr = head;
      head = head->next;
      free(curr);
    }
    return 0;
}

Answer 1

Code Comments:

curr = malloc(sizeof(Node));

malloc() returns void* thus you need to cast it before assignment.

curr = (Node*) malloc(sizeof(Node));

Most (all I have seen) coding standards mention not to use this:

Node * head, * curr;
head = NULL;

I agree with them as it just makes things hard to read (thus maintain). So one variable per line. And initialize on declaration (where appropriate).

Node  *head = NULL;
Node  *curr;

OK. The next one is arguable (so feel free to use best judgement).

Personally I find that hard to read:

 if (!head->next)

I think it would be easier to read as:

if (head->next == NULL)

But surprisingly I normally I prefer using the ! when the object is a pointer (or bool). I think in this case it is because it is combined with testing a nested member of a structure it just does not look correct (but as I said it is an arguable case).

Edge Case

What happens if the list is empty?

Node * reverse_list(Node * head) {

  if (!head->next) //only one elem
    return head;

You have chosen the wrong edge case.
The one you should be checking is checking for NULL. A list of one node is no different than a list of many. The edge case with pointers is nearly always the NULL case.

Algorithm

Iterative

The code before your while loop looks like the code inside the while loop. This sort of suggests you can replace it with a do-while loop. Thus your iterative code should look more like this:

Node* reverse(Node* list)
{
    if (list == NULL)
    {   
        return NULL;
    }   

    Node*   last    = NULL;
    do  
    {   
        Node*   next    = list->next;
        list->next      = last;
        last            = list;
        list            = next;
    }   
    while(list != NULL);

    return last;
}

Recursive

Converting a loop into recursion requires an extra function to cope with the extra variable used for last. So the main recursion looks like this (it just calls the actually recursive function setting up the last parameter). You should have this wrapper function to help users of the code from calling the recursive part of the function incorrectly.

Node* r_reverse(Node* list)
{
    return r_reverseItem(NULL, list);
}

Now we can do the recursion. Again the edge case is still NULL.

Node* r_reverseItem(Node* last, Node* list)
{
    if (list == NULL)
    {   
        return last;
    }   

    Node*   next    = list->next;
    list->next      = last;
    return r_reverseItem(list,next);
}

Answer 2

Good fix for the edge case of only one element, but what happens if there's only two elements? I'm seeing another edge case concern.

//inside reverse_list
...
last = head;
curr = head->next;
head = curr->next; //or head->next->next - null if two elements

last->next = NULL
while (head->next) { //head is null here if list length = 2

I see no other major concerns in your algorithm(s).