学步园

今天在看一篇文章中说RethinkDB公司在面试的过程中发现很多程序员不能通过下面的题目：

请写出一个C函数，实现反转一个单向链接表的功能。

我就试试自己能否做出来。我现在越来越不相信写的代码了，必须经过我的测试之后，我稍微放心。所以我也写了测试程序，我希望下面的代码能够达到好的可读性。

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

#define ARRAY_SIZE(array) ((sizeof(array)) / sizeof(array[0]))
#define MAX_ARRAY_SIZE 10
#define MAX_ARRAY_ELEMENT 100

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

typedef struct Node Node;
typedef struct Node* List;


/* Function declarations */

List add_node(int val, List list);
List create_list(int *array, int len);
List reverse_list(List list);
void print_list(List list);
void del_list(List *list);

void run_test();


int main(int argc, char *argv[]) {
    srand((unsigned int)time(NULL));
    
    int i;
    for (i = 0; i < 5; i++) {
        printf("\n====test %d====\n", i);
        run_test();
    }
}

void run_test() {
    int i, array[MAX_ARRAY_SIZE];

    int array_size = rand() % MAX_ARRAY_SIZE;
    for (i = 0; i < array_size; i++) {
        array[i] = rand() % MAX_ARRAY_ELEMENT;
    }

    printf("length = %d\n", array_size);
    List list = create_list(array, array_size); 
    print_list(list);

    list = reverse_list(list);
    print_list(list);

    del_list(&list);
    print_list(list);
}

List create_list(int *array, int len) {
    if (array == NULL) return NULL;
    List list = NULL;
    int i;
    for (i = 0; i < len; i++) {
        list = add_node(array[i], list);
    }
    return list;
}

List add_node(int val, List list) {
    Node *node = (Node *)malloc(sizeof(Node));
    if (node == NULL) { 
        fprintf(stderr, "malloc error.\n");
        exit(1); // when malloc fail, I simply exit here.
    }
    node->val = val;
    node->next = list;
    list = node;
    return list;
}

List reverse_list(List list) {
    if (list == NULL) {
        return NULL;
    }

    Node *cur_node = list;
    Node *pre_node = NULL;
    Node *next_node = NULL;

    while (cur_node != NULL) {
        next_node = cur_node->next;
        cur_node->next = pre_node;

        pre_node = cur_node;
        cur_node = next_node;
    }
    return pre_node;
}

void print_list(List list) {
    Node *node = list;
    if (node) {
        printf("list = [");
        printf("%d", node->val);
        node = node->next;
    } else {
        printf("Empty List!\n");
        return;
    }
    while (node) {
        printf(" -> %d", node->val);
        node = node->next;
    }
    printf("]\n");
}

void del_list(List *list) {
    if (*list == NULL) return;

    Node *cur_node, *next_node;
    cur_node = *list;
    while (cur_node) {
        next_node = cur_node->next;
        free(cur_node);
        cur_node = next_node;
    }
    *list = NULL;
}

下面是在我机器上的测试结果：

====test 0====
length = 0
Empty List!
Empty List!
Empty List!

====test 1====
length = 9
list = [41 -> 75 -> 53 -> 4 -> 57 -> 65 -> 0 -> 73 -> 32]
list = [32 -> 73 -> 0 -> 65 -> 57 -> 4 -> 53 -> 75 -> 41]
Empty List!

====test 2====
length = 0
Empty List!
Empty List!
Empty List!

====test 3====
length = 6
list = [82 -> 21 -> 26 -> 78 -> 62 -> 27]
list = [27 -> 62 -> 78 -> 26 -> 21 -> 82]
Empty List!

====test 4====
length = 6
list = [56 -> 87 -> 2 -> 65 -> 99 -> 36]
list = [36 -> 99 -> 65 -> 2 -> 87 -> 56]
Empty List!