C语言解决链表置逆问题

Question

本题要求：编写一个函数，实现链表置逆功能

函数接口定义：

void Reverse(LinkList H);

其中H是待置逆的链表

裁判测试程序样例：

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

typedef int DataType;
struct Node {
    DataType      data;
    struct Node*  next;
};
typedef struct Node  *PNode;
typedef struct Node  *LinkList;

LinkList SetNullList_Link()
{
    LinkList head = (LinkList)malloc(sizeof(struct Node));
    if (head != NULL) head->next = NULL;
    else printf("alloc failure");
    return head;
}

void CreateList(struct Node *head)
{
    PNode p = NULL;  int data;
    scanf("%d", &data); 
    while (data != -1) {
        p = (struct Node*)malloc(sizeof(struct Node));
        p->data = data;
        p->next = head->next;
        head->next = p;
        scanf("%d", &data);
    }
}
void Reverse(LinkList H)
{
    @@
}
void print(LinkList head)
{
    PNode  p = head->next;
    while (p)
    {
        printf("%d ", p->data);
        p = p->next;
    }
}
void DestoryList_Link(LinkList head)
{
    PNode  pre = head;
    PNode p = pre->next;
    while (p)
    {
        free(pre);
        pre = p;
        p = pre->next;
    }
    free(pre);
}

int main()
{
    LinkList head = NULL;
    head = SetNullList_Link();
    CreateList(head);
    Reverse(head);
    print(head);
    DestoryList_Link(head);
    return 0;
}

输入样例：
1 2 3 4 5 -1
输出样例：
1 2 3 4 5

Answer 1

不断将后续节点用头插法插入即可

void Reverse(LinkList H)
{
    LinkList p = H->next;
    if(p == NULL || p->next == NULL)
        return;
    LinkList q = p;
    p = p->next;
    q->next = NULL;
    while(p!=NULL)
    {
        q = p->next;
        p->next = H->next;
        H->next = p;
        p = q;
    }
}