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 条评论
登录 后参与评论

相关文章

来自专栏JavaEdge

AbstractList源码解析1 实现的方法2 两种内部迭代器3 两种内部类3 SubList 源码分析4 RandomAccessSubList 源码:AbstractList 作为 Lis

它实现了 List 的一些位置相关操作(比如 get,set,add,remove),是第一个实现随机访问方法的集合类,但不支持添加和替换

3672
来自专栏xingoo, 一个梦想做发明家的程序员

B树 B-树 B+树 B*树

B树 即二叉搜索树:        1.所有非叶子结点至多拥有两个儿子(Left和Right);        2.所有结点存储一个关键字;        3...

1977
来自专栏老马说编程

(42) 排序二叉树 / 计算机程序的思维逻辑

40节介绍了HashMap,41节介绍了HashSet,它们的共同实现机制是哈希表,一个共同的限制是没有顺序,我们提到,它们都有一个能保持顺序的对应类TreeM...

1956
来自专栏从流域到海域

《数据结构》 单链表常用操作代码集合

Ps:每段代码中,添加了Solo署名的是博主自己写的,其余来自课本或老师。 //单链表存储结构 typedef struct Node //结点类型定义 ...

2476
来自专栏决胜机器学习

PHP数据结构(六) ——树与二叉树之概念及存储结构

PHP数据结构(六)——树与二叉树之概念及存储结构 (原创内容,转载请注明来源,谢谢) 一、树的含义 1、树为非线性结构,是n(n>=0)个节点的有限集,非空树...

48410
来自专栏后端之路

最熟悉的ArrayList

上来先问几个问题 ArrayList是否存在最大容量? 如果ArrayList存在最大容量 那么达到最大之后会如何处理 ArrayList的性能影响因素 Arr...

1895
来自专栏Android机动车

数据结构——遍历二叉树

二叉树的遍历:是指从根结点出发,按照某种次序依次访问二叉树中的所有结点,使得每个结点被访问一次且仅被访问一次。

821
来自专栏令仔很忙

集合详解(二)----ArrayList源代码剖析(JDK1.7)

ArrayList是List类的一个典型的实现,是基于数组实现的List类,因此,ArrayList封装了一个动态的、可变长度的Object[]数组。Arra...

631
来自专栏Java学习网

用Java实现处理日期的工具类——常用日期处理方法

日期处理是开发过程中经常遇到的问题,以下是总结了开发中常用的方法,代码如下: import java.text.ParseException; import j...

2935
来自专栏趣学算法

数据结构 第4讲 单链表

链表是线性表的链式存储方式,逻辑上相邻的数据在计算机内的存储位置不一定相邻,那么怎么表示逻辑上的相邻关系呢?可以给每个元素附加一个指针域,指向下一个元素的存储位...

953

扫码关注云+社区