[数据结构与算法]实现对单链表的倒置

我们知道数组的倒置比较简单，只需要知道数组的头，和数组的尾，将其数据互换，再将第二个和倒数第二个互换，一直这样操作下去，数组就实现倒置了。那么单链表也可以通过这样的方法实现倒置吗？显然是不合理的。因为单链表我们无法通过一个节点找到他的前驱节点(节点前面连的节点)，也就无法实现从倒数第一个到倒数第二个的操作。

那么我们该如何实现呢？我们可以将一个要倒置的链表断为两个链表。第一个链表，是头结点和第一个节点。第二个链表是，第二个节点和其后面所有节点构成的。

再依次将第二个链表的第一个节点插入到头结点的后面（第二个链表的第一个节点插入后，第二个节点就变成了第二个链表的第一个节点），这样就实现了链表的倒置。

?

?下面我们用代码实现（后面附上创建链表的代码）

void invert_linklist(LinkList Ll)
{
    
    LinkList p = Ll->pNext;
    Ll->pNext = NULL;
    LinkList q;
    
    //相当于将一个链表，一分为二
    while (NULL != p)
    {
        //q指向的节点是要断开，进行插入的节点
        q = p;

        //p后移，不操作p
        //p的目的是能够找到后面断掉的链表
        p = p->pNext;

        //将q指向的节点插入到头结点的后面。分两步

        //第一步：将q指向的节点的指针域指向头结点的指针域本来的后驱节点（第一次循环执行时，等同于将q的指针域指向空）
        q->pNext = Ll->pNext;

        //第二步：将头指针的指针域指向q指向的节点
        Ll->pNext = q;

    }

    //结束函数
    return;
}

?其他代码

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

typedef struct Node
{
    int data; //数据域
    struct Node * pNext; //指针域
}LNode, * LinkList;

//函数声明
LinkList create_linklist(); //创建一个链表
void invert_linklist(LinkList); //倒置链表
void show_linklist(LinkList); //将链表的值域输出

int main(void)
{
    LinkList Ll = NULL; //定义一个指向空的节点指针
    Ll = create_linklist();
    show_linklist(Ll);

    invert_linklist(Ll);
    show_linklist(Ll);

    return 0;
}

LinkList create_linklist()
{
    int len; //用来存储节点的个数
    int i; //for循环中的循环变量
    int val; //用来存放节点的值域


    //为头结点分配内存
    LinkList Ll = (LinkList)malloc(sizeof(LNode));
    
    //判断是否分配成功
    if(!Ll)
    {
        printf("动态内存分配失败，程序退出！\n");
        exit(-1);
    }

    Ll->pNext = NULL;

    //请求用户输入节点个数
    printf("请输入节点的个数：\n");
    scanf("%d", &len);

    //定义一个始终指向当前链表尾节点的指针，初始指向头结点
    LinkList pTail = Ll;
    pTail->pNext = NULL;

    for (i = 0; i < len; i++)
    {
        //每循环一次生成一个新的节点
        LinkList LNew = (LinkList)malloc(sizeof(LNode));

        //判断是否分配成功
        if(NULL == LNew)
        {
            printf("动态内存分配失败，程序退出！\n");
            exit(-1);
        }

        //请求用户输入新节点的值
        printf("请输入第%d个节点的值\n", i+1);
        scanf("%d", &val);

        //将用户输入的值存储到数据域
        LNew->data = val;

        //将原始链表的最后一个节点挂在新节点上
        pTail->pNext = LNew;

        //新节点变成当前的尾节点，需要将其指针域变为空
        LNew->pNext = NULL;

        //pTail后移，使其指向当前的尾节点
        pTail = LNew;
    }

    //提示用户链表创建成功
    printf("链表创建成功！\n");

    //返回指向头结点的指针
    return Ll;   
}

void show_linklist(LinkList Ll)
{
    LinkList p = Ll->pNext;

    while(p != NULL)
    {
        printf("%d ", p->data);
        p = p->pNext;
    }

    printf("\n");

    return;
}