1074 Reversing Linked List (25分)[静态链表]

By Jalan

文章目录

• **By Jalan**
• 知识工具需求
• • 数学
  • 数据结构和算法
  • 语言
• 题干
• • 输入条件
  • • 例1
  • 输出条件
  • • 例1
• 题解
• • 第一次
  • • 思路
    • 预期时间复杂度
    • 编写用时
    • 代码
    • • CPP
      • • 运行用时
• 结尾

知识工具需求

数学

数据结构和算法

• 链表
• 栈

语言

• 可以通过%05d这种格式来进行前补零共5位(可超不少)的格式化输出

题干

给一个链表L和一个常数K,每K个数字反转链表,比如

L being 1→2→3→4→5→6, if K3输出3→2→1→6→5→4;

if K4, 输出 4→3→2→1→5→6.

输入条件

第一行包含:第一个节点的地址(5位非负),节点总数N[0,10^5],正整数K<=N是反转长.NULL是-1

下面是N行

Address Data Next

例1

00100 6 4

00000 4 99999

00100 1 12309

68237 6 -1

33218 3 00000

99999 5 68237

12309 2 33218

输出条件

输出反转之后的链表

例1

00000 4 33218

33218 3 12309

12309 2 00100

00100 1 99999

99999 5 68237

68237 6 -1

题解

第一次

思路

注意题目里的反转实际上操作的是next,每个节点的address和key实际上是不变的,只要把反转之后的元素排好然后把i的next设置成i+1的id就行.末尾不满K个的是不反转的

首先申请一个大数组存放静态链表.

每K个一组遍历这个链表

(通过下面两步实现反转)

申请一个栈,每K个存到栈里,

出栈所有元素到一个resultList里.

把末尾不足K的不经过栈直接放到resultList里

把resultList第i个的next变成i+1的id(也可以在输出的时候每行第三个输出i+1的id)

控制输出最后一个.

预期时间复杂度

nlogn

编写用时

30分钟

代码

CPP

#include <stack>
#include <stdio.h>
#include <vector>
using namespace std;

typedef struct node
{
    int id;
    int key;
    int next;
} node;

int main(int argc, char const *argv[])
{
    //input
    int nowId, N, K;
    scanf("%d%d%d", &nowId, &N, &K);
    vector<node> linkedList(100001);
    for (int i = 0, tempId, tempKey, tempNext; i < N; i++)
    {
        scanf("%d%d%d", &tempId, &tempKey, &tempNext);
        linkedList[tempId].id = tempId;
        linkedList[tempId].key = tempKey;
        linkedList[tempId].next = tempNext;
    }

    //process
    vector<node> resultList;
    stack<node> s;
    if (nowId == -1)
    {
        return 0;
    }
    else
    {
        while (nowId != -1) //这里面也可以是1反正只有一个出口
        {
        	//从nowId向前查找K个看能不能找到.
            int Kcounter = 0;
            int nowIdPlusK = nowId;
            if (nowId != -1)
            {
                ++Kcounter;
                nowIdPlusK = linkedList[nowId].next;
            }
            for (int i = 0; i < K - 1; i++)//好像写重了,改成K把前面那个域去了也行.
            {
                if (nowIdPlusK != -1)
                {
                    ++Kcounter;
                    nowIdPlusK = linkedList[nowIdPlusK].next;
                }
            }
            //从while到下面这一段所有的作用就是来找后面还有没有K个数.当然更好的方法好像是遍历一遍用除法做
            if (Kcounter == K)
            {
                for (int i = 0; i < K; i++)
                {
                    s.push(linkedList[nowId]);
                    nowId = linkedList[nowId].next;
                }
                for (int i = 0; i < K; i++)
                {
                    resultList.push_back(s.top());
                    s.pop();
                }
            }
            else
            {
                while (nowId != -1)
                {
                    resultList.push_back(linkedList[nowId]);
                    nowId = linkedList[nowId].next;
                }
                break;
            }
        }
    }

    //output
    for (int i = 0; i < resultList.size() - 1; i++)
    {
        printf("%05d %d %05d\n", resultList[i].id, resultList[i].key, resultList[i + 1].id);
    }
    printf("%05d %d -1", (resultList.end() - 1)->id, (resultList.end() - 1)->key);
    return 0;
}

           

运行用时

结尾

看在我写了这么多注释的份上可以给我点个赞嘛,求求惹=]砰砰砰,给我加点写下去的油呀@[email protected]

也欢迎关注我的CSDN账号呀,接下来两个月我应该会按这个格式更新所有的PTA甲级题目

**开心code每一天**