静态单链表 C++版本 Python版本
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了静态单链表 C++版本 Python版本,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2186字,纯文字阅读大概需要4分钟。
内容图文
![静态单链表 C++版本 Python版本](/upload/InfoBanner/zyjiaocheng/646/3c8512092c6d48daa72b823a8cf350bc.jpg)
AcWing 826单链表 https://www.acwing.com/problem/content/828/
实现一个单链表,链表初始为空,支持三种操作:
(1) 向链表头插入一个数;
(2) 删除第k个插入的数后面的数;
(3) 在第k个插入的数后插入一个数
现在要对该链表进行M次操作,进行完所有操作后,从头到尾输出整个链表。
注意:题目中第k个插入的数并不是指当前链表的第k个数。例如操作过程中一共插入了n个数,则按照插入的时间顺序,这n个数依次为:第1个插入的数,第2个插入的数,…第n个插入的数。
输入格式
第一行包含整数M,表示操作次数。
接下来M行,每行包含一个操作命令,操作命令可能为以下几种:
(1) “H x”,表示向链表头插入一个数x。
(2) “D k”,表示删除第k个输入的数后面的数(当k为0时,表示删除头结点)。
(3) “I k x”,表示在第k个输入的数后面插入一个数x(此操作中k均大于0)。
输出格式
共一行,将整个链表从头到尾输出。
数据范围
1≤M≤1000001≤M≤100000
所有操作保证合法。
#include <iostream> #include <cstdio> #include <algorithm> using namespace std; const int N = 1e5+5; int e[N], ne[N], head, index; void init() { head = -1; index = 0; } void add_head(int x) { e[index] = x; ne[index] = head; head = index; ++ index; } //删除第k个输入数后面的数 void dele(int k) { //下标为k-1 ne[k-1] = ne[ne[k-1]]; } //在第k个输入的数后面插入一个数x void add(int k, int x) { e[index] = x; ne[index] = ne[k-1]; ne[k-1] = index; ++ index; } void show() { for(int i = head; i != -1; i = ne[i]) cout << e[i] << " "; } int main() { int m; cin >> m; init(); while(m --) { char ch; cin >> ch; switch(ch) { case 'H': { int x; cin >> x; add_head(x); break; } case 'D': { int k; cin >> k; if(!k) head = ne[head]; else dele(k); break; } case 'I': { int k, x; cin >> k >> x; add(k, x); break; } } } show(); return 0; }
m = int(input()) global head global index e = [0 for i in range(m+5)] ne = [0 for i in range(m+5)] def add_head(x): global head global index e[index] = x ne[index] = head head = index index += 1 def add(k, x): global head global index e[index] = x ne[index] = ne[k-1] ne[k-1] = index index += 1 def dele(k): global head global index if not k: head = ne[head] else: ne[k-1] = ne[ne[k-1]] head = -1 index = 0 while m: m -= 1 opera = input().split() op = opera[0] if op == 'H': x = int(opera[1]) add_head(x) elif op == 'D': k = int(opera[1]) dele(k) else: k = int(opera[1]) x = int(opera[2]) add(k, x) i = head while i != -1: print(e[i], end=" ") i = ne[i] print("")
内容总结
以上是互联网集市为您收集整理的静态单链表 C++版本 Python版本全部内容,希望文章能够帮你解决静态单链表 C++版本 Python版本所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。