C++ 实现L2-002 链表去重

2025-10-15 04:30:20

给定一个带整数键值的链表 L，你需要把其中绝对值重复的键值结点删掉。即对每个键值 K，只有第一个绝对值等于 K 的结点被保留。同时，所有被删除的结点须被保存在另一个链表上。例如给定 L 为 21→-15→-15→-7→15，你需要输出去重后的链表 21→-15→-7，还有被删除的链表 -15→15。

输入格式：

输入在第一行给出 L 的第一个结点的地址和一个正整数 N（≤105，为结点总数）。一个结点的地址是非负的 5 位整数，空地址 NULL 用 −1 来表示。

随后 N 行，每行按以下格式描述一个结点：

地址键值下一个结点

其中地址是该结点的地址，键值是绝对值不超过104的整数，下一个结点是下个结点的地址。

输出格式：

首先输出去重后的链表，然后输出被删除的链表。每个结点占一行，按输入的格式输出。

输入样例：

00100 5
99999 -7 87654
23854 -15 00000
87654 15 -1
00000 -15 99999
00100 21 23854

输出样例：

00100 21 23854
23854 -15 99999
99999 -7 -1
00000 -15 87654
87654 15 -1

思路：
很多办法都可以实现，我选择数组模拟动态内存，先建立一个链表再遍历，时间复杂度是O(n)，格式控制还是printf好用。

#include<iostream>
#include<cstdio>
#include<cmath>
#define NULL -1

using namespace std;

typedef struct node {
	int val;
	unsigned int next;
}node;

node store[100001];//开辟一片模拟内存
int flag[10001];//标记结点

int main() {
	int num, startM;//p标记当前节点
	cin >> startM >> num;

	for (int i = 0; i < num; i++) {
		int now, val, next;
		cin >> now >> val >> next;
		store[now].val = val;
		store[now].next = next;
	}//链表构建完成

	int p1=startM,startS=NULL;
	int p2 = 100000,pre;
	bool k = true;
	while (p1 != NULL) {
		if (flag[abs(store[p1].val)] != 0) {
			store[pre].next = store[p1].next;
			store[p2].next = p1;
			store[p1].next = NULL;
			p2 = p1;
			if (k) {
				k = false;
				startS = p2;
			}
			p1 = store[pre].next;
		}
		else {
			flag[abs(store[p1].val)] = 1;
			pre = p1;
			p1 = store[p1].next;
		}
	}//链表查重完成

	p1 = startM;
	while (p1 != NULL) {
		if(store[p1].next!=NULL)
			printf("%05d %d %05d\n",p1, store[p1].val, store[p1].next);
		else
			printf("%05d %d %d\n", p1, store[p1].val, store[p1].next);
		p1 = store[p1].next;
	}
	p1 = startS;
	while (p1 != NULL) {
		if (store[p1].next != NULL)
			printf("%05d %d %05d\n", p1, store[p1].val, store[p1].next);
		else
			printf("%05d %d %d\n", p1, store[p1].val, store[p1].next);
		p1 = store[p1].next;
	}
	return 0;
}

到此这篇关于C++ 实现L2-002 链表去重的文章就介绍到这了,更多相关C++ 链表去重内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

C++双向链表实现简单通讯录

本文实例为大家分享了C++双向链表实现简单通讯录的具体代码,供大家参考,具体内容如下 #include<iostream> #include<fstream> #include <stdlib.h> #include<string> using namespace std; typedef struct Directory { string Name; string Mobile; string Wechatnumber; string STREET; st
c++ 如何合并两个有序链表

1.题目要求这是一道求职面试时经常要求手写或者机试的经典题目. 已知两个链表head1和head2各自有序,请把它们合并成一个链表依然有序.结果链表要包含head1和head2的所有节点,即使节点值相同. 注意:不能开辟新空间来存储合并后的链表.如果第一次做该题,很容易会想到使用新链表来存储合并后的有序链表.虽然可以如此实现,但是不符合常规解法和面试官的要求. 2.非递归实现算法过程: 输入:两个有序的单链表head1与head2: 输出:合并后的有序单链表mergeHead: 算法描
C++单链表实现大数加法

本文实例为大家分享了C++单链表实现大数加法,供大家参考,具体内容如下 Input Format 输入文件包括两行. 第一行包括一个正整数,保证位数不超过1000000. 第二行包括一个正整数,保证位数不超过1000000. Output Format 输出文件包括一行. 第一行包括一个正整数. Sample Input 10558 22 Sample Output 10580 #include <iostream> using namespace std; class BigData { f
C++实现合并两个排序的链表

本文实例为大家分享了C++合并两个排序的链表,供大家参考,具体内容如下问题描述输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则. struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { } }; 方法一 class Solution { public: ListNode* Merge(ListNode* pHead1, ListN
C++实现静态链表

本文实例为大家分享了C++实现静态链表的具体代码,供大家参考,具体内容如下一.动态链表和静态链表区别: (1)动态链表: (2)静态链表: 应用:二叉树二.思路: 1.结点设置:T data: int link; 2.链表要用一个avil来保存可分配空间的首地址: 3.初始化:引入头结点:elem[0]: 头结点先指向空NULL, 用-1表示: avil存储空分配的空间的首地址1: 然后让其它可分配空间的结点的link指向坐标大一的结点: 三.实现程序: #ifndef Stat
C++实现单链表的构造

单链表的构造,包括最常用函数,setData(),Insert(),Remove(),getData(),Search(). 代码如下: #include <iostream> #include <stdlib.h> using namespace std; template<class T> struct LinkNode{ T data; LinkNode<T> *link; LinkNode(LinkNode<T> *ptr=NULL){l
C语言数据结构实现链表去重的实例

C语言数据结构实现链表去重的实例题目及分析链表去重时间限制 300 ms 内存限制 65536 kB 代码长度限制 8000 B 判题程序 Standard 给定一个带整数键值的单链表L,本题要求你编写程序,删除那些键值的绝对值有重复的结点.即对任意键值K,只有键值或其绝对值等于K的第一个结点可以被保留.同时,所有被删除的结点必须被保存在另外一个链表中.例如:另L为21→-15→-15→-7→15,则你必须输出去重后的链表21→-15→-7.以及被删除的链表-15→15. 输入格式: 输入
C++ 实现L2-002 链表去重

给定一个带整数键值的链表 L,你需要把其中绝对值重复的键值结点删掉.即对每个键值 K,只有第一个绝对值等于 K 的结点被保留.同时,所有被删除的结点须被保存在另一个链表上.例如给定 L 为 21→-15→-15→-7→15,你需要输出去重后的链表 21→-15→-7,还有被删除的链表 -15→15. 输入格式: 输入在第一行给出 L 的第一个结点的地址和一个正整数 N(≤105,为结点总数).一个结点的地址是非负的 5 位整数,空地址 NULL 用 −1 来表示. 随后 N 行,每行按以下
JS实现的合并两个有序链表算法示例

本文实例讲述了JS实现的合并两个有序链表算法.分享给大家供大家参考,具体如下: 将两个有序链表合并为一个新的有序链表并返回.新链表是通过拼接给定的两个链表的所有节点组成的. 示例: 输入:1->2->4, 1->3->4 输出:1->1->2->3->4->4 可以直接运行的方案: <script> function Node(element) { this.element = element;//当前节点的元素 this.next = n
python实现合并两个有序列表的示例代码

题目描述将两个升序链表合并为一个新的升序链表并返回.新链表是通过拼接给定的两个链表的所有节点组成的. LeetCode原题地址:https://leetcode-cn.com/problems/merge-two-sorted-lists/ 测试用例示例1 输入:l1 = [1,2,4], l2 = [1,3,4] 输出:[1,1,2,3,4,4] 示例2 输入:l1 = [], l2 = [] 输出:[] 示例3 输入:l1 = [], l2 = [0] 输出:[0] 代码详解因为Lee
java中List对象列表实现去重或取出及排序的方法

前言因为在面试的时候碰到几次list的去重和排序,觉着有必要给大家总结一下具体的方法,分享出来供大家学习参考,话不多说了,来一起看看下面介绍的一种做法: 一.list去重 1.1 实体类Student List<Student>容量10k以上,要求去重复.这里Student的重复标准是属性相同,因此需要重写equals和hashcode方法,不知道有几个可以手写出来. student的equals方法: public void equals(Object o){ if(this == o)
python3.4.3下逐行读入txt文本并去重的方法

读写文件时应注意的问题包括: 1.字符编码 2.操作完成即时关闭文件描述符 3.代码兼容性几种方法: #!/bin/python3 original_list1=[" "] original_list2=[" "] original_list3=[" "] original_list4=[" "] newlist1=[" "] newlist2=[" "] newlist3=[&quo
利用Distinct()内置方法对List集合的去重问题详解

前言说到对集合去重处理,第一时间想到的肯定是Linq的Distinct扩展方式,对于一般的值类型集合去重,很好处理,直接list.Distinct()即可.但是如果想要对一个引用类型的集合去重(属性值都相同就认为重复),就会发现,直接Distinct()是不行的先来看看泛型链表 List<T> 的定义: public class List<T> : IList<T>, ICollection<T>, IList, ICollection, IReadOn
Java实现链表的常见操作算法详解

链表分为单链表,双向链表和循环链表,是一种链式存储结构,由一个个结点链式构成,结点包含数据域和指针域,其中单链表是只有一个指向后驱结点的指针,双向链表除头结点和尾结点外,每个结点都有一个前驱指针和一个后继指针,循环链表的尾结点的指针指向头结点. 相比数组而言,链表的插入和删除比较快,查询慢. 本文主要以单链表为例,介绍下链表的常用算法操作. 单链表的结构: 在java语言中,链表的每个结点用Node类来表示: package com.linkedlist; public class Node {
python批量查询、汉字去重处理CSV文件

CSV文件用记事本打开后一般为由逗号隔开的字符串,其处理方法用Python的代码如下.为方便各种程度的人阅读在代码中有非常详细的注释. 1.查询指定列,并保存到新的csv文件. # -*- coding: utf-8 -*- ''''' Author: Good_Night Time: 2018/1/30 03:50 Edition: 1.0 ''' # 导入必须的csv库 import csv # 创建临时文件temp.csv找出所需要的列 temp_file = open("temp.csv
Python实现合并两个有序链表的方法示例

本文实例讲述了Python实现合并两个有序链表的方法.分享给大家供大家参考,具体如下: 思路:先选出第一个节点,然后遍历两个链表,把小的作为当前节点的下一个节点,一直到其中一个链表遍历完,这时候把另一个链表直接接上就好 # Definition for singly-linked list. # class ListNode(object): # def __init__(self, x): # self.val = x # self.next = None class Solution(obj

C++ 实现L2-002 链表去重

输入格式：

输出格式：

输入样例：

输出样例：

相关推荐

随机推荐