PAT 1097 Deduplication on a Linked List

这篇具有很好参考价值的文章主要介绍了PAT 1097 Deduplication on a Linked List。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

个人学习记录,代码难免不尽人意
Given a singly linked list L with integer keys, you are supposed to remove the nodes with duplicated absolute values of the keys. That is, for each value K, only the first node of which the value or absolute value of its key equals K will be kept. At the mean time, all the removed nodes must be kept in a separate list. For example, given L being 21→-15→-15→-7→15, you must output 21→-15→-7, and the removed list -15→15.

Input Specification:
Each input file contains one test case. For each case, the first line contains the address of the first node, and a positive N (≤10 5 ) which is the total number of nodes. 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 Key Next
where Address is the position of the node, Key is an integer of which absolute value is no more than 10 4, and Next is the position of the next node.

Output Specification:
For each case, output the resulting linked list first, then the removed list. Each node occupies a line, and is printed in the same format as in the input.

Sample Input:
00100 5
99999 -7 87654
23854 -15 00000
87654 15 -1
00000 -15 99999
00100 21 23854
Sample Output:
00100 21 23854
23854 -15 99999
99999 -7 -1
00000 -15 87654
87654 15 -1

#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<cmath>
#include<map>
#include<set>
using namespace std;
struct node{
	int data;
	int address;
	int next; 
}Node[100010];

int main(){
  int first,n,k;
  scanf("%d %d",&first,&n);
  for(int i=0;i<n;i++){
  	 int address,data,next;
  	 scanf("%d%d%d",&address,&data,&next);
  	 node a;
  	 a.address=address;
  	 a.data=data;
  	 a.next=next;
  	 Node[address]=a;
  }
  

  set<int> s;
  s.insert(abs(Node[first].data));
  int now=Node[first].address;
  int newfirst=-1;
  int newtemp=-1;
  bool flag=true;
  while(Node[now].next!=-1){
  	node no=Node[now];
  	if(s.find(abs(Node[no.next].data))==s.end()){
  		s.insert(abs(Node[no.next].data));
  		now=no.next;
	  }
	else{
		Node[now].next=Node[no.next].next;
		if(flag){
			newfirst=no.next;
			newtemp=newfirst;
			flag=false;
		}
		else{
		Node[newtemp].next=no.next;
			newtemp=no.next;
			
		}
	
		
	}
  }
  now=Node[first].address;
  while(now!=-1){
  	if(Node[now].next==-1)
  		printf("%05d %d -1\n",Node[now].address,Node[now].data);
  	else 
	  printf("%05d %d %05d\n",Node[now].address,Node[now].data,Node[now].next);
  	now=Node[now].next;
  }
  if(newfirst!=-1){
  	Node[newtemp].next=-1;
  	int newnow=Node[newfirst].address;
  while(newnow!=-1){
  	if(Node[newnow].next==-1)
  		printf("%05d %d -1\n",Node[newnow].address,Node[newnow].data);
  	else 
	  printf("%05d %d %05d\n",Node[newnow].address,Node[newnow].data,Node[newnow].next);
  	newnow=Node[newnow].next;
  }
  }
  
}

本题真的踩了不少坑,我的做法和《算法笔记》略有不同,其中要注意的地方有1.注意边界,比如当前node的next值为-1,再让node=node.next就很有可能出错,应该事先判断。一定要注意边界值。并且,我的做法还要判断是不是有要删除的节点(即原链表中是否出现了两个绝对值一样的数),如果没有的话有些操作不应该出现。文章来源地址https://www.toymoban.com/news/detail-657266.html

到了这里,关于PAT 1097 Deduplication on a Linked List的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 1116 Come on! Let‘s C (PAT甲级)

    \\\"Let\\\'s C\\\" is a popular and fun programming contest hosted by the College of Computer Science and Technology, Zhejiang University. Since the idea of the contest is for fun, the award rules are funny as the following: 0、 The Champion will receive a \\\"Mystery Award\\\" (such as a BIG collection of students\\\' research papers...). 1、 Those who ranked as a prime nu

    2024年02月07日
    浏览(30)
  • 1047 Student List for Course (PAT甲级)

    Zhejiang University has 40,000 students and provides 2,500 courses. Now given the registered course list of each student, you are supposed to output the student name lists of all the courses. Input Specification: Each input file contains one test case. For each case, the first line contains 2 numbers: N (≤40,000), the total number of students, and K (≤

    2024年02月16日
    浏览(36)
  • PTA 1052 Linked List Sorting

    个人学习记录,代码难免不尽人意。 A linked list consists of a series of structures, which are not necessarily adjacent in memory. We assume that each structure contains an integer key and a Next pointer to the next structure. Now given a linked list, you are supposed to sort the structures according to their key values in increasing order. Inp

    2024年02月15日
    浏览(36)
  • 数据结构与算法 | 链表(Linked List)

    链表(Linked List)是一种线性数据结构,它由一系列节点(Node)组成,每个节点包含两部分:数据和指向下(上)一个节点的引用(或指针)。链表中的节点按照线性顺序连接在一起(相邻节点不需要存储在连续内存位置),不像数组一样存储在连续的内存位置。链表通常由

    2024年02月08日
    浏览(48)
  • 【LeetCode 算法】Linked List Cycle II 环形链表 II

    给定一个链表的头节点 head ,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。 如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从

    2024年02月14日
    浏览(43)
  • PAT B1049

    题目 给定一个正数数列,我们可以从中截取任意的连续的几个数,称为片段。例如,给定数列 { 0.1, 0.2, 0.3, 0.4 },我们有 (0.1) (0.1, 0.2) (0.1, 0.2, 0.3) (0.1, 0.2, 0.3, 0.4) (0.2) (0.2, 0.3) (0.2, 0.3, 0.4) (0.3) (0.3, 0.4) (0.4) 这 10 个片段。 给定正整数数列,求出全部片段包含的所有的数之和。

    2024年02月02日
    浏览(39)
  • pat乙级1002

    关键思路: 大数输入问题 1010010100 用int和long long都是远远不够的,因此用字符数组来输入,然后再转换成整数 数字与拼音的转换 本题用最基本的方法,使用switch开关语句实现转换 拼音数字间有 1 空格,但一行中最后一个拼音数字后没有空格。 此类问题一般使用以下代码实

    2023年04月14日
    浏览(53)
  • NAT与PAT

        NAT(Nct.work Adldrnns Trans l at.i on)又称为网络地址转换,用于实规私不网络和公不网络之问的互访。 公有网络地址(以下简称公网地址)是指在互联网上全球唯一的IP地址。2019年11月26日,是人类互联网时代值得纪念的一-天,全球近43亿个IPv4地址己正式耗尽。 私有网络地址(以下简

    2024年02月11日
    浏览(36)
  • pat乙题1002

    笔记: 1.字符数组char s[]的长度用sizeof(), strlen() 字符串string s长度s.size()和s.length()都是求的实际的占位,不算0的 2.switch: 用一个显化记录的字符串不就行了。 3.把数字sum粘贴到字符串数组s 上 改:用动态字符串存入。 4.既然用的char s[],想把字符串里的数字加和,当然要用-‘

    2024年02月16日
    浏览(36)
  • PAT 甲级【1010 Radix】

    本题范围long型(35)^10 枚举radix范围上限pow(n/a0,1/m)上,考虑上限加1.范围较大。使用二分查找枚举 代码如下 本页面将简要介绍二分查找,由二分法衍生的三分法以及二分答案。 二分查找(英语:binary search),也称折半搜索(英语:half-interval search)、对数搜索(英语:logar

    2024年02月08日
    浏览(38)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包