编程练习（1）——单链表反转

单链表反转是链表的一种基本操作。网上看了一些文章，介绍的还是都很详细。自己也尝试着写了一些代码，调试通过。链表的反转方法有很多种。采用游标指针遍历，修改next指针是常用的方法。一般地，需要定义三个指针，比如本文中，定义为

Node *cur,*pNext,*pre;

其中，cur用来保存反转后的头指针；pNext是游标，用来遍历链表并将各个节点的next指针值修改为前一个节点地址；而pre指针用来在pNext修改next指针前，将next指向的下一个节点指针（即尚未反转的子链的头指针）临时保存。

既然pNext为遍历游标，故而循环条件即为判断pNext非空。

需要注意的是，第一个数据节点反转结束后成为尾节点，因而其next指针需要置空。

我写的代码的两种思路：一是如前面所述，定义三个指针；另外一种思路是不单独定义临时指针pre，而是用第一个数据节点（即反转后的尾节点）的next指针作为临时指针。同时，cur指针也可以不用，直接用h-next保存转换后的第一个数据指针即可。

上代码：

头文件LinkedNode.h

#ifndef LINKEDNODE_H_INCLUDED
#define LINKEDNODE_H_INCLUDED
#endif // LINKEDNODE_H_INCLUDED

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

typedef int DATA; //定义通用数据类型

typedef struct _node
{
    DATA data;
    struct _node *next;
}Node,*LinkedNode;

LinkedNode Create();//创建空链表，返回头指针
LinkedNode CreateN(int *N);//构造一个能读入N个初始数据节点的链表，当输入的数据不足N个或有非法数据时，只取前面的有效数据，并修改N值
void Print(LinkedNode h);//按节点先后顺序呢输出
int Reverse_1(LinkedNode h);//反转链表
int Reverse_2(LinkedNode h);
int Reverse_3(LinkedNode h);
int Reverse_4(LinkedNode h);

四个反转方法Reverse_1和Reverse_2是思路一，区别是Reverse_2省略了cur变量。Reverse_3和Reverse_4是思路二，区别是Reverse_4初始化的变量不同，从而循环变量和循环顺序不一样。这样主要是为了练习，说明写代码时变量的定义方式和循环方式都是可以改变的。有些时候可以优化代码。

算法文件LinkedNode.c

#include "LinkedNode.h"

//创建空链表，返回头指针
LinkedNode Create()
{
    LinkedNode h;
    h=malloc(sizeof(Node));
    if(h==NULL) return NULL;
    else
    {
        h->next=NULL;
    }
    return h;
}

////构造一个能读入N个初始数据节点的链表，当输入的数据不足N个时，数据置NULL
LinkedNode CreateN(int *N)
{
    LinkedNode h=Create();
    if(h==NULL)return NULL;
    int i=1;
    DATA d;
    Node *p=h;
    printf("\nfunc:CreateN:请输入数据个数：\n");
    if(scanf("%d",N)==1)
    {
        if(*N<1)
        {
            printf("\nfunc:CreateN:您输入的数字必须是大于0的整数，程序将结束！\n");
            return;
        }
        printf("\nfunc:CreateN:您打算输入的数据个数为%d，请依次输入数据，并按回车键结束\n",*N);
        while(i<=*N&&scanf("%d",&d)==1)
        {
            Node *pTemp=malloc(sizeof(Node));
            if(pTemp!=NULL)
            {
                pTemp->data=d;
                p->next=pTemp;
                p=p->next;
                i++;
            }
            p->next=NULL;
        }
        *N=--i;
        printf("\nfunc:CreateN:您已经输入%d个有效数据，以下是您刚才输入的有效数据：\n",*N);
        Print(h);
    }
    return h;
}

//按节点先后顺序输出
void Print(LinkedNode h)
{
    if(h==NULL||h->next==NULL)
    {
        printf("\nfunc:Print:链表不存在或者为空！\n");
        return;
    }
    Node *p=h->next;
    printf("\n");
    while(p)
    {
        printf("%d\t",p->data);
        p=p->next;
    }
    printf("\n");
}

//反转链表,带表头指针,用三个指针
//cur:记录头指针；pNext：游标，操作指针；pre：临时指针，用来临时记录未转换的链表的头位置
//返回值：循环次数
//循环前对游标变量pNext初始化，如果将pre也初始化，则可以更改训话顺序
//注意翻转后的尾指针（即原始的第一个数据指针）的next需要置空
int Reverse_1(LinkedNode h)
{
    int i=0;//记录循环次数
    if(h==NULL||h->next==NULL)
    {
        printf("\nfunc:Reverse:链表不存在或者为空！\n");
        return;
    }
    Node *cur,*pNext,*pre;
    cur=h->next;
    pNext=cur->next;
    cur->next=NULL;
    while(pNext)
    {
        pre=pNext->next;
        pNext->next=cur;
        cur=pNext;
        pNext=pre;
        i++;
    }
    h->next=cur;
    return i;
}
//与Reverse_1本质一致，但不定义cur指针，而是直接修改h->next,从而减少栈中变量数量
int Reverse_2(LinkedNode h)
{
    int i=0;
    if(h==NULL||h->next==NULL)
    {
        printf("\nfunc:Reverse_2:链表不存在或者为空！\n");
        return;
    }
    Node *pNext,*pre;//pNext为游标指针，用来操作next指针反转，pre指针为临时指针，用来临时记录未操作部分的表头
    pNext=h->next->next;//定义游标初始位置,即转换后的尾指针位置
    h->next->next=NULL;//尾指针不使用，置空
    while(pNext)
    {
        pre=pNext->next;
        pNext->next=h->next;
        h->next=pNext;
        pNext=pre;
        i++;
    }
    return i;
}
//反转链表，带表头,这种方法是将后面的节点依次插入h的后面
//为了说明使用h->next->next作为存储临时指针，这里定义Node *tail=h->next
//这样好处是不用另外定义一个临时指针pre，且循环结束时，tail自动只想NULL，不用专门置空操作
int Reverse_3(LinkedNode h)
{
    int i=0;
    if(h==NULL||h->next==NULL)
    {
        printf("\nfunc:Reverse_2:链表不存在或者为空！\n");
        return;
    }
    Node *tail,*pNext;
    tail=h->next;
    pNext=tail->next;//游标指针初始位置,如果此处不初始化，应该把pNext=tail->next放在循环开始，且循环条件为tail->next!=NULL
    while(pNext!=NULL)
    {
        tail->next=pNext->next;
        pNext->next=h->next;
        h->next=pNext;
        pNext=tail->next;
        i++;
    }
    return i;
}
//方法同Reverse_3，但pNext在循环前不初始化，故而循环条件和顺利都改变
int Reverse_4(LinkedNode h)
{
    int i=0;
    if(h==NULL||h->next==NULL)
    {
        printf("\nfunc:Reverse_2:链表不存在或者为空！\n");
        return;
    }
    Node *tail=h->next;
    Node *pNext;
    while(tail->next!=NULL)
    {
        pNext=tail->next;
        tail->next=pNext->next;
        pNext->next=h->next;
        h->next=pNext;
        i++;
    }
    return i;
}

下面是main.c 文件，包含一个测试函数

#include "LinkedNode.h"
#include "tree.h"

void testReverse();

int main()
{
    testReverse();
    return 0;
}
void testReverse()
{
    int N=0;
    int nCount;
    LinkedNode h=CreateN(&N);
    if(N<1)
    {
        printf("\nfunc:testReverse:您输入的数字必须是大于0的整数，程序将结束！\n");
        //return;

    }
    nCount=Reverse_4(h);
    if(nCount<1)
    {
        printf("\nfunc:testReverse:共进行了0次链表反转循环,程序将结束\n");
        //return;
    }
    printf("\nfunc:testReverse:在本次链表反转时，共进行了%d次循环\n",nCount);
    printf("\nfunc:testReverse:以下是反转后的结果\n");
    printf("\n=========================================================\n");
    Print(h);
}

几个函数测试都通过。编译环境是GCC。下面是两组输入情形：

欢迎交流！