单链表原地逆置

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

typedef int dataType;

// 单链表
typedef struct linkNode
{
    dataType data;
    struct linkNode *next;
}node,*linkList;

// 1.初始化不带头结点的单链表
void init(linkList *list)
{
    *list = NULL; // 表示链表指针指向空处
}

// 2.输出单链表元素
void display(linkList list)
{
    node *p = list; // p为工作指针，初值为头指针
    if(!p)
    {
        printf("链表为空！\n");
        return;
    }
    while (p)
    {
        printf("%d ",p->data);
        p = p->next;
    }
}

// 3.根据用户输入构造单链表
void scanInsert(linkList *head)
{
    node *p,*q;
    dataType x;
    printf("请输入(以9999作为结束标识)...\n");
    scanf("%d",&x);
    while (x!=9999)
    {
        q = (node*) malloc(sizeof(node));
        q->data = x;
        q->next = NULL;
        if(!*head) // 创建第一个结点时
        {
            *head = q;
            p = *head;
        }
        else
        {
            p->next = q;
            p = p->next;
        }
        scanf("%d",&x);
    }
}

// 3.8.6 单链表原地逆置
void reverse(linkList *head)
{
    node *p = *head, *s;
    *head = NULL;
    while (p)
    {
        s = p;
        p = p->next;
        s->next = *head;
        *head = s;
    }
}

// 3.8.6.1 带头结点的单链表原地逆置
void reverse1(linkList *head)
{
    node *p = (*head)->next, *q;
    (*head)->next = NULL;
    while (p) // 依次取下结点插入头结点后面(关键步骤)
    {
        q = p;
        p = p->next;
        q->next = (*head)->next;
        (*head)->next = q;
    }
}

int main()
{
    linkList list;
    init(&list);
    scanInsert(&list);
    reverse(&list);
    display(list);
    return 0;
}