【PAT】1074. Reversing Linked List (25)【链表的使用】

2024-04-12 06:18

本文主要是介绍【PAT】1074. Reversing Linked List (25)【链表的使用】,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目描述

Given a constant K and a singly linked list L, you are supposed to reverse the links of every K elements on L. For example, given L being 1→2→3→4→5→6, if K = 3, then you must output 3→2→1→6→5→4; if K = 4, you must output 4→3→2→1→5→6.

翻译:给一个常量K和一个单链表L,你需要将每K个L上的元素倒置。举个例子,如果给定的L为 1→2→3→4→5→6,如果K为3,则你必须输出 3→2→1→6→5→4; 如果K为4,则你必须输出4→3→2→1→5→6。

INPUT FORMAT

Each input file contains one test case. For each case, the first line contains the address of the first node, a positive N (<= 105) which is the total number of nodes, and a positive K (<=N) which is the length of the sublist to be reversed. The address of a node is a 5-digit nonnegative integer, and NULL is represented by -1.

Then N lines follow, each describes a node in the format:

Address Data Next

where Address is the position of the node, Data is an integer, and Next is the position of the next node.

翻译:每个输入文件包含一组测试数据。对于每组输入数据,第一行包括头结点的地址,一个正整数N(<=10^5),代表总节点数,和一个正整数K(<=N),代表节点总数,和一个正整数K(<=N),代表需要转置的长度K。节点的地址为一个5位非负整数,-1代表NULL。

OUTPUT FORMAT

For each case, output the resulting ordered linked list. Each node occupies a line, and is printed in the same format as in the input.

翻译:对于每组输入数据,输出按照要求执行后的链表。每个节点占一行,并且根据输入格式输出。


Sample Input:

00100 6 4
00000 4 99999
00100 1 12309
68237 6 -1
33218 3 00000
99999 5 68237
12309 2 33218

Sample Output:

00000 4 33218
33218 3 12309
12309 2 00100
00100 1 99999
99999 5 68237
68237 6 -1


解题思路

先搜索一遍链表,将节点按照原链表顺序添加到vector中,再根据题目描述,如果vector长度大于等于K,则倒序将前K个压入结果vector中,并将前K个节点删除,小于K时就正序压入。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<vector> 
#include<algorithm>
#define INF 99999999
using namespace std;
struct node{int id,key;node(){}node(int ID,int k):id(ID),key(k){}
}d[100010];
vector<node> v;
vector<node> ans;
int S,N,K;
int main(){scanf("%d%d%d",&S,&N,&K);int id1,key,id2;for(int i=0;i<N;i++){scanf("%d%d%d",&id1,&key,&id2);d[id1].id=id2;d[id1].key=key; }while(S!=-1){v.push_back(node(S,d[S].key));S=d[S].id;}while(v.size()>=K){for(int i=K-1;i>=0;i--){ans.push_back(v[i]);}v.erase(v.begin(),v.begin()+K);}for(int i=0;i<v.size();i++){ans.push_back(v[i]);} for(int i=0;i<ans.size();i++){if(i==ans.size()-1)printf("%05d %d -1\n",ans[i].id,ans[i].key);else printf("%05d %d %05d\n",ans[i].id,ans[i].key,ans[i+1].id);}return 0;
}

这篇关于【PAT】1074. Reversing Linked List (25)【链表的使用】的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/896332

相关文章

中文分词jieba库的使用与实景应用(一)

知识星球:https://articles.zsxq.com/id_fxvgc803qmr2.html 目录 一.定义: 精确模式(默认模式): 全模式: 搜索引擎模式: paddle 模式(基于深度学习的分词模式): 二 自定义词典 三.文本解析   调整词出现的频率 四. 关键词提取 A. 基于TF-IDF算法的关键词提取 B. 基于TextRank算法的关键词提取

使用SecondaryNameNode恢复NameNode的数据

1)需求: NameNode进程挂了并且存储的数据也丢失了,如何恢复NameNode 此种方式恢复的数据可能存在小部分数据的丢失。 2)故障模拟 (1)kill -9 NameNode进程 [lytfly@hadoop102 current]$ kill -9 19886 (2)删除NameNode存储的数据(/opt/module/hadoop-3.1.4/data/tmp/dfs/na

Hadoop数据压缩使用介绍

一、压缩原则 (1)运算密集型的Job,少用压缩 (2)IO密集型的Job,多用压缩 二、压缩算法比较 三、压缩位置选择 四、压缩参数配置 1)为了支持多种压缩/解压缩算法,Hadoop引入了编码/解码器 2)要在Hadoop中启用压缩,可以配置如下参数

Makefile简明使用教程

文章目录 规则makefile文件的基本语法:加在命令前的特殊符号:.PHONY伪目标: Makefilev1 直观写法v2 加上中间过程v3 伪目标v4 变量 make 选项-f-n-C Make 是一种流行的构建工具,常用于将源代码转换成可执行文件或者其他形式的输出文件(如库文件、文档等)。Make 可以自动化地执行编译、链接等一系列操作。 规则 makefile文件

使用opencv优化图片(画面变清晰)

文章目录 需求影响照片清晰度的因素 实现降噪测试代码 锐化空间锐化Unsharp Masking频率域锐化对比测试 对比度增强常用算法对比测试 需求 对图像进行优化,使其看起来更清晰,同时保持尺寸不变,通常涉及到图像处理技术如锐化、降噪、对比度增强等 影响照片清晰度的因素 影响照片清晰度的因素有很多,主要可以从以下几个方面来分析 1. 拍摄设备 相机传感器:相机传

【C++】_list常用方法解析及模拟实现

相信自己的力量,只要对自己始终保持信心,尽自己最大努力去完成任何事,就算事情最终结果是失败了,努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一:什么是list? •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二:list常用接口 •🌰1.默认成员函数 🔥构造函数(⭐) 🔥析构函数 •🌰2.list对象

csu1329(双向链表)

题意:给n个盒子,编号为1到n,四个操作:1、将x盒子移到y的左边;2、将x盒子移到y的右边;3、交换x和y盒子的位置;4、将所有的盒子反过来放。 思路分析:用双向链表解决。每个操作的时间复杂度为O(1),用数组来模拟链表,下面的代码是参考刘老师的标程写的。 代码如下: #include<iostream>#include<algorithm>#include<stdio.h>#

pdfmake生成pdf的使用

实际项目中有时会有根据填写的表单数据或者其他格式的数据,将数据自动填充到pdf文件中根据固定模板生成pdf文件的需求 文章目录 利用pdfmake生成pdf文件1.下载安装pdfmake第三方包2.封装生成pdf文件的共用配置3.生成pdf文件的文件模板内容4.调用方法生成pdf 利用pdfmake生成pdf文件 1.下载安装pdfmake第三方包 npm i pdfma

零基础学习Redis(10) -- zset类型命令使用

zset是有序集合,内部除了存储元素外,还会存储一个score,存储在zset中的元素会按照score的大小升序排列,不同元素的score可以重复,score相同的元素会按照元素的字典序排列。 1. zset常用命令 1.1 zadd  zadd key [NX | XX] [GT | LT]   [CH] [INCR] score member [score member ...]

git使用的说明总结

Git使用说明 下载安装(下载地址) macOS: Git - Downloading macOS Windows: Git - Downloading Windows Linux/Unix: Git (git-scm.com) 创建新仓库 本地创建新仓库:创建新文件夹,进入文件夹目录,执行指令 git init ,用以创建新的git 克隆仓库 执行指令用以创建一个本地仓库的