(PTA数据结构与算法题目集)6-1 单链表逆转——看条件,新的链表还是修改原来链表

6-1 单链表逆转 (20 分)

本题要求实现一个函数,将给定的单链表逆转。

函数接口定义:

List Reverse( List L );

其中List结构定义如下:

typedef struct Node *PtrToNode;
struct Node {
    ElementType Data; /* 存储结点数据 */
    PtrToNode   Next; /* 指向下一个结点的指针 */
};
typedef PtrToNode List; /* 定义单链表类型 */

L是给定单链表,函数Reverse要返回被逆转后的链表。

裁判测试程序样例:

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

typedef int ElementType;
typedef struct Node *PtrToNode;
struct Node {
    ElementType Data;
    PtrToNode   Next;
};
typedef PtrToNode List;

List Read(); /* 细节在此不表 */
void Print( List L ); /* 细节在此不表 */

List Reverse( List L );

int main()
{
    List L1, L2;
    L1 = Read();
    L2 = Reverse(L1);
    Print(L1);
    Print(L2);
    return 0;
}

/* 你的代码将被嵌在这里 */

输入样例:

5
1 3 4 5 2

输出样例:

1
2 5 4 3 1

正确代码:

List Reverse(List L)
{
    List ReL;
    PtrToNode pa,pb,pc;
    if(L==NULL || L->Next==NULL)
        return L;
    pa = L;
    pb = pa->Next;
    pc = pb->Next;
    pa->Next = NULL;
    while(pb)
    {
        pb->Next = pa;
        pa = pb;
        pb = pc;
        if(pc)
            pc = pc->Next;
    }
    ReL = pa;
    return ReL;
}

 同时附上我写的Read()和Print():

List Read()
{
    int n;
    scanf("%d",&n);
    int i;
    List L = NULL;
    PtrToNode p=NULL;
    PtrToNode pa = L;
    for(i=0; i<n; i++)
    {
        p = (PtrToNode)malloc(sizeof(struct Node));
        scanf("%d",&(p->Data));
        p->Next = NULL;
        if(i == 0)
        {
            L = p;
            pa = p;
        }
        else
        {
            pa->Next = p;
            pa = pa->Next;
        }

    }
    return L;
}
void Print( List L )
{
    PtrToNode pa = L;
    while(pa)
    {
        printf("%d ",pa->Data);
        pa = pa->Next;
    }
    printf("\n");

} 


思路:

将链表逆转,是将原链表修改,而不是放入新的一个链表中(开始我是这样想的,开了一个新的链表来存放逆转后的链表)。

主要是要看清输出,第一行是1,这时候原来了的L1变成了尾指针,只指向最后一个(原来的开始)节点。

方法:利用指针遍历链表,每一步,都把Next指针掉个头。先定义三个临时指针,pa指向第一个,pb指向第二个,pc指向第三个;然后修改pb->Next = pa,是将链表的指针(指向下一个的箭头)掉个头,指向前一个;pc记录下原来的pb->Next,防止断链;然后pa,pb,pc都往下走一个,直至遍历完毕。

 

下面是我写的原来的开辟新链表的函数:

List Reverse1( List L )
{

    List ReL = NULL;
    PtrToNode pa,pb;
    pa = L;
    while(pa)
    {
        pb = (PtrToNode)malloc(sizeof(struct Node));
        pb->Data = pa->Data;
        pb->Next = ReL;
        ReL = pb;
        pa = pa->Next;
    }
    return ReL;

}

 

全部评论

相关推荐

不愿透露姓名的神秘牛友
07-10 11:27
明天又是董事长面,啥时候是个头啊
在太阳里长大的人:公司就仨人吧😂
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-07 13:47
机械打工仔:你自己匿名可以,这么好的公司就别给它匿名了
点赞 评论 收藏
分享
Lorn的意义:你这种岗位在中国现在要么牛马天天加班,要么关系户进去好吃好喝,8年时间,真的天翻地覆了,对于资本来说你就说一头体力更好的牛马,哎,退伍没有包分配你真的亏了。
点赞 评论 收藏
分享
06-13 17:33
门头沟学院 Java
顺序不记了,大致顺序是这样的,有的相同知识点写分开了1.基本数据类型2.基本数据类型和包装类型的区别3.==和equals区别4.ArrayList与LinkedList区别5.hashmap底层原理,put操作时会发生什么6.说出几种树型数据结构7.B树和B+树区别8.jvm加载类机制9.线程池核心参数10.创建线程池的几种方式11.callable与runnable区别12.线程池怎么回收线程13.redis三剑客14.布隆过滤器原理,不要背八股,说说真正使用时遇到了问题没有(我说没有,不知道该怎么回答了)15.堆的内存结构16.自己在写项目时有没有遇见过oom,如何处理,不要背八股,根据真实经验,我说不会17.redis死锁怎么办,watchdog机制如何发现是否锁过期18.如何避免redis红锁19.一个表性别与年龄如何加索引20.自己的项目的QPS怎么测的,有没有真正遇到大数量表21.说一说泛型22.springboot自动装配原理23.springmvc与springboot区别24.aop使用过嘛?动态代理与静态代理区别25.spring循环依赖怎么解决26.你说用过es,es如何分片,怎么存的数据,1000万条数据怎么写入库中27.你说用limit,那么在数据量大之后,如何优化28.rabbitmq如何批次发送,批量读取,答了延迟队列和线程池,都不对29.计网知不知道smtp协议,不知道写了对不对,完全听懵了30.springcloud知道嘛?只是了解反问1.做什么的?短信服务,信息量能到千万级2.对我的建议,基础不错,但是不要只背八股,多去实际开发中理解。面试官人不错,虽然没露脸,但是中间会引导我回答问题,不会的也只是说对我要求没那么高。面完问我在济宁生活有没有困难,最快什么时候到,让人事给我聊薪资了。下午人事打电话,问我27届的会不会跑路,还在想办法如何使我不跑路,不想扣我薪资等。之后我再联系吧,还挺想去的😭,我真不跑路哥😢附一张河科大幽默大专图,科大就是大专罢了
查看30道真题和解析
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务