PTA 带头结点的单链表就地逆置(10 分)

本题要求编写函数实现带头结点的单链线性表的就地逆置操作函数。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取巧用个数组作为中转站:
void ListReverse_L(LinkList &L)
{
    LNode *F = L->next;
    LNode *opr = L->next;
    //LNode *real = L;
    int arr[110];
    int index = 0;
    while(F!=NULL)
    {
       // printf("%d\n",F->data);
        arr[index++] = F->data;
        F=F->next;
    }
    int len = index;
   // printf("%d\n",len);
    while(opr!=NULL)
    {
        //printf("%d\n",opr->data);
        opr->data = arr[--index];
        opr = opr->next;
    }
    //L = real;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

1006. 捡石头

1006. 捡石头 (Standard IO) 时间限制: 1000 ms  空间限制: 262144 KB  具体限制  题目描述 憨厚的老农夫昨天捡到了3...

2735
来自专栏Java开发者杂谈

算法之逆序对

算法之逆序对 逆序对问题 ​ 假设A[1..n]是一个有n个不同数的数组。若iA[j],则对偶(i, j)称为A的一个逆序对(inversion)。 列出数组{...

3439
来自专栏技术博客

C# 泛型的简单理解(安全、集合、方法、约束、继承)

泛型允许你在编译时实现类型安全。它们允许你创建一个数据结构而不限于一特定的数据类型。然而,当使用该数据结构时,编译器保证它使用的类型与类型安全是相一致的。泛型提...

701
来自专栏算法与数据结构

PTA 循环单链表区间删除 (15 分)

本题要求实现带头结点的循环单链表的创建和单链表的区间删除。L是一个带头结点的循环单链表,函数ListCreate_CL用于创建一个循环单链表,函数ListDel...

1898
来自专栏猿人谷

单链表

线性表的链式表示和实现       线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的,也可以使不连续的)。因此,为...

2435
来自专栏开发与安全

数据结构:线性表之链式存储结构

为了表示每个数据元素ai与其直接后继元素ai+1之间的逻辑关系,对数据ai,除了存储其自身的信息之外,还需存储一个指示其 直接后继的信息(即直接后继的存储位置)...

18110
来自专栏软件开发 -- 分享 互助 成长

欧拉回路

一、定义 欧拉回路:图G,若存在一条路,经过G中每条边有且仅有一次,称这条路为欧拉路,如果存在一条回路经过G每条边有且仅有一次, 称这条回路为欧拉回路。具有欧拉...

1849
来自专栏算法与数据结构

数据结构 链表(循环)

#include<stdio.h> #include<malloc.h> #include<stdlib.h> //函数状态码定义 #define TRUE ...

1867
来自专栏开发与安全

数据结构:线性表之顺序存储结构

线性表的数据对象集合为 {a1,a2,....an},每个元素的类型均为Datatype。其中,除第一个元素a1外,每一个元素有且只有一个直接前驱元素,除了最后...

1788
来自专栏我是业余自学C/C++的

循环链表(测试代码,Qt5.1 for windows)

2004

扫码关注云+社区