链表逆置

一、引入

学习数据结构做到了一个题，要求写一个函数将链表逆置，要求不开辟新的空间，根据题目解析做出了这个题，这篇文章记录一下这个逆置的方法。

二、方法详解

简单来讲，就是对于一个有空的头结点的链表，我们遍历他后面的所有节点，然后将遍历得到的每一个节点都插入头结点后面，这样当遍历完之后就可以实现链表逆置的操作。

图解：

逆置下图的链表

对于只有一个或者两个节点的链表是不需要逆置的，所以可以特殊判断一下。其他情况，我们可以从剩余节点第三个开始插入。首先断开连接

然后我们将他插在头结点后面

同理第四个，第五个节点

最后就得到了逆置的链表

三、代码实现

这里借助pta的一个题来写代码

点击展开题目

本题要求编写函数实现带头结点的单链线性表的就地逆置操作函数。L是一个带头结点的单链表，函数ListReverse_L(LinkList &L)要求在不新开辟节点的前提下将单链表中的元素进行逆置，如原单链表元素依次为1,2,3,4，则逆置后为4,3,2,1。

函数接口定义：

void ListReverse_L(LinkList &L);

其中 L 是一个带头结点的单链表。

裁判测试程序样例：

//库函数头文件包含
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>

//函数状态码定义
#define TRUE        1
#define FALSE       0
#define OK          1
#define ERROR       0
#define INFEASIBLE -1
#define OVERFLOW   -2

typedef int  Status;
typedef int  ElemType; //假设线性表中的元素均为整型

typedef struct LNode
{
    ElemType data;
    struct LNode *next;
}LNode,*LinkList;

Status ListCreate_L(LinkList &L,int n)
{
    LNode *rearPtr,*curPtr;   //一个尾指针，一个指向新节点的指针
    L=(LNode*)malloc(sizeof (LNode));
    if(!L)exit(OVERFLOW);
    L->next=NULL;               //先建立一个带头结点的单链表
    rearPtr=L;  //初始时头结点为尾节点,rearPtr指向尾巴节点
    for (int i=1;i<=n;i++){  //每次循环都开辟一个新节点，并把新节点拼到尾节点后
        curPtr=(LNode*)malloc(sizeof(LNode));//生成新结点
        if(!curPtr)exit(OVERFLOW);
        scanf("%d",&curPtr->data);//输入元素值
        curPtr->next=NULL;  //最后一个节点的next赋空
        rearPtr->next=curPtr;
        rearPtr=curPtr;
    }
    return OK;
}
void ListReverse_L(LinkList &L);
void ListPrint_L(LinkList &L){
//输出单链表
    LNode *p=L->next;  //p指向第一个元素结点
    while(p!=NULL)
    {
          if(p->next!=NULL)
               printf("%d ",p->data);
          else
               printf("%d",p->data);
          p=p->next;
    }
}
int main()
{
    LinkList L;
    int n;
    scanf("%d",&n);
    if(ListCreate_L(L,n)!= OK) {
          printf("表创建失败！！！\n");
          return -1;
    }
    ListReverse_L(L);
    ListPrint_L(L);
    return 0;
}
/* 请在这里填写答案 */

输入格式：

第一行输入一个整数n，表示单链表中元素个数，接下来一行共n个整数，中间用空格隔开。

输出格式：

输出逆置后顺序表的各个元素，两个元素之间用空格隔开，最后一个元素后面没有空格。

输入样例：

4
1 2 3 4

输出样例：

4 3 2 1

代码长度限制

16 KB

时间限制

400 ms

内存限制

64 MB

题目AC代码：

点击展开代码

// 库函数头文件包含
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>

// 函数状态码定义
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2

typedef int Status;
typedef int ElemType; // 假设线性表中的元素均为整型

typedef struct LNode
{
    ElemType data;
    struct LNode *next;
} LNode, *LinkList;

Status ListCreate_L(LinkList &L, int n)
{
    LNode *rearPtr, *curPtr; // 一个尾指针，一个指向新节点的指针
    L = (LNode *)malloc(sizeof(LNode));
    if (!L)
        exit(OVERFLOW);
    L->next = NULL; // 先建立一个带头结点的单链表
    rearPtr = L;    // 初始时头结点为尾节点,rearPtr指向尾巴节点
    for (int i = 1; i <= n; i++)
    {                                            // 每次循环都开辟一个新节点，并把新节点拼到尾节点后
        curPtr = (LNode *)malloc(sizeof(LNode)); // 生成新结点
        if (!curPtr)
            exit(OVERFLOW);
        scanf("%d", &curPtr->data); // 输入元素值
        curPtr->next = NULL;        // 最后一个节点的next赋空
        rearPtr->next = curPtr;
        rearPtr = curPtr;
    }
    return OK;
}
void ListReverse_L(LinkList &L);
void ListPrint_L(LinkList &L)
{
    // 输出单链表
    LNode *p = L->next; // p指向第一个元素结点
    while (p != NULL)
    {
        if (p->next != NULL)
            printf("%d ", p->data);
        else
            printf("%d", p->data);
        p = p->next;
    }
}
int main()
{
    LinkList L;
    int n;
    scanf("%d", &n);
    if (ListCreate_L(L, n) != OK)
    {
        printf("表创建失败！！！\n");
        return -1;
    }
    ListReverse_L(L);
    ListPrint_L(L);
    return 0;
}
/* 请在这里填写答案 */
void ListReverse_L(LinkList &L)
{
    if (L->next == NULL || L->next->next == NULL)
        return;
    LinkList p = L->next->next;
    L->next->next = NULL;
    while (p != NULL)
    {
        LinkList pt = p->next;
        p->next = L->next;
        L->next = p;
        p = pt;
        // LinkList pt1 = L->next;
        // LinkList pt2 = p->next;
        // L->next = p;
        // p->next = pt1;
        // p = pt2;
    }
}

void ListReverse_L(LinkList &L)
{
    if (L->next == NULL || L->next->next == NULL) // 特殊判断，一个及两个节点的可以直接跳过
        return;
    LinkList p = L->next->next; // p指向遍历到的节点
    L->next->next = NULL; // 第二个节点肯定是逆置后的最后一个，设为空，防止输出出错
    while (p != NULL)
    {
        LinkList pt = p->next; // pt用来代指后面还没被便利的那串链表的第一个节点
        p->next = L->next; // 插入
        L->next = p;
        p = pt; // 继续遍历
    }
}