C语言实现单链表逆置算法

题目：

        设计算法，将单链表L就地逆置，结果如图所示：

代码：

#include<stdio.h>
#include<stdlib.h>
typedef int dataType;    //数据类型为int

//结点结构体
typedef struct node
{
    dataType data;      //数据域
    struct node *next;  //指针域
}LinkList;

//初始化结点
void listInitiate(LinkList **head)            //双星指针，地址的地址，在初始化时，我们要使地址的值改变，所以使用双星作为参数传入
{
    *head = (LinkList*)malloc(sizeof(LinkList));  //为头结点分配位置空间（一个结点的大小）
    (*head)->next = NULL;                 //头结点指针域初始默认为空
}

/*尾插法建立单链表——得到的链表是顺序的
利用数组的前n个数建立一条单链表*/
void listBuildRear(LinkList *head, dataType arr[], int n)
{
    LinkList *p = head;                       //新增一个指针，用来代替head指针
    for (int i = 0; i < n; i++)              //循环n次，每次循环都在链表尾部追加一个结点
    {
        LinkList *q = (LinkList*)malloc(sizeof(LinkList));//新建立结点，并为之分配内存空间
        q->data = arr[i];                 //数据域赋值，将数组的第i+1个数字赋给新结点q
        q->next = NULL;                   //单链表最后一个结点的指针域都为空
        p->next = q;                      //将原始单链表最后一个结点指针域指向新结点q，从此q成为最后一个结点，原始最后一个结点变成倒数第二个结点
        p = q;                            //p又指向当前链表最后一个结点，为下一次尾部插入做准备
    }
}

//遍历输出函数
void listPrint(LinkList *head)
{
    printf("单链表元素是：");
    LinkList *p = head;                       //新增一个指针，用来代替head指针
    while (p->next != NULL)
    {
        printf("%d   ", p->next->data);
        p = p->next;                      //这一句不要忘了，不然会死循环的，我总是忘掉这一句
    }
    printf("\n");
}

//就地逆置函数
void ReverseList(LinkList &L)
{
	LinkList *p,*q;
	p=L.next;
	L.next=NULL;   
	while(p!=NULL)
	{
		q=p;
		p=p->next;
		q->next=L.next;  
		L.next=q;
	}
}

int main()
{
    LinkList link1;
    LinkList *p;
    dataType arr[] = {6,7,8,9,10};
    p = &link1;
    listInitiate(&p);
    listBuildRear(p,arr,5);      //利用数组arr的前七个数据建立一条链表
    printf("原");
    listPrint(p);                //打印原链表
    printf("\n就地逆置之后的");
    ReverseList(*p);              //打印逆置后的链表
    listPrint(p);
    return 0;
}

效果图：