测试您是否眼高手低：写一个单链表逆置函数

就这么简单，请您写一个将单链表逆置的函数。要求采用两种实现方式：

（1） 采用循环的方式; （10分钟）

（2） 采用递归的方式。（30分钟）

不知您能一次在以上的时间完成吗？您肯定不屑一顾，呵呵。

为了您测试方便，我准备了以下的代码给您调用。您只需要写这样的函数接口：

/**
 * Param:  the list to be reversed

 * Return: the reversed list


*/

SList * slist_reverse_loop(SList *slist)


{ // your code here ... }
SList * slist_reverse_recursion(SList *slist)


{ // your code here ... }

然后在 main.c 里面这样调用：

slist_reverse_test(slist_revers_loop);
slist_reverse_test(slist_revers_recursion);

头文件 slist.h :

#ifndef _slist_h
#define _slist_h

typedef struct _SList SList;
struct _SList
{
    int data;
    
    SList *next;
} ;

SList * slist_new_n(int);
void slist_free(SList *);
void slist_printf(SList *);

void slist_reverse_test(SList *(*)(SList *));

#endif


测试文件： main.c

#include "slist.h"


/**
 * 在这里添加您的实现 .....
 */

SList * slist_reverse_loop(SList *slist)

{

//


}

SList * slist_reverse_recursion(SList *slist)


{

//


}




int
main(void)
{
    slist_reverse_test(slist_reverse_loop);
    slist_reverse_test(slist_reverse_recursion);
    return 0;
}


编译:(没有写 Makefile， 凑合着编译一下吧 ;-)
$ gcc -o test main.c slist.c -Wall
$ ./test

下面列出实现文件， 您还是先不用看了，直接 copy 后编译吧。最后列了一下我写出的参考答案。如果您有更好的答案，请给我回复一下，谢谢。

实现文件： slist.c

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

#include "slist.h"

void
slist_printf(SList *slist)
{
    SList *tmp;

    for (tmp = slist; tmp != NULL; tmp = tmp->next)
    {
        printf("%d ", tmp->data);
    }
    printf("\n");
}

void
slist_free(SList *slist)
{
    SList *tmp, *next;

    for (tmp = slist; tmp != NULL; tmp = next)
    {
        next = tmp->next;
        free(tmp);
    }
}

SList*
slist_new_n(int n)
{
    SList *slist = NULL, *tmp;
    int i;

    for (i = 0; i < n; ++i)
    {
        tmp = (SList*) malloc(sizeof(SList));
        tmp->data = i;
        tmp->next = slist;
        slist = tmp;
    }

    return slist;
}

void
slist_reverse_test(
        SList * (*slist_reverse)(SList *)
        )
{
    SList *slist = NULL;
    int i;

    for (i = 0; i < 6; ++i)
    {
        slist = slist_new_n(i);
        
        printf("%d nodes in list%d : \n", i, i);
        slist_printf(slist);
        printf("reverse it: \n");
        slist = (*slist_reverse)(slist);
        slist_printf(slist);
        printf("\n");

        slist_free(slist);
        slist = NULL;
    }
}

/**
 * I think the following is the exact answer ...
 * But maybe you will get the better!
 */
static SList *
slist_reverse_loop(SList *slist)
{
    SList *prev = NULL;
    SList *next = NULL;

    while (slist != NULL)
    {
        next = slist->next;

        slist->next = prev;
        prev = slist;
        slist = next;
    }

    return prev;
}

static SList*
slist_reverse_recursion(SList* slist)
{
    SList *tail;

    if (NULL == slist || NULL == slist->next)
        return slist;
   
    tail = slist_reverse_recursion(slist->next);
    slist->next->next = slist;
    slist->next = NULL;

    return tail;
}