题目描述
实现一个单链表,链表初始为空,支持三种操作:
(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≤100000
所有操作保证合法。
输入样例:
10
H 9
I 1 1
D 1
D 0
H 6
I 3 6
I 4 5
I 4 5
I 3 4
D 6
输出样例:
6 4 6 5
观众老爷们,如果本思路对您有帮助,求关注一波~~~
思路
利用数组模拟单链表
e为存储的元素值 ne存储当前节点的下一个节点在数组e中的存储位置 idx标记位置值
模拟以下
head -> 1 -> 5 -> -1
头插法,从5向1插入
1. head = -1
2. 插入5 head -> 5 -> -1
e[0] = 5
ne[0] = -1
head = 0
3 插入1 head -> 1 -> 5 -> -1
e[1] = 1
ne[1] = 0
head = 1
e = [5, 1]
ne= [-1, 0]
head = 1
从head头节点遍历
第一个元素1
i = head = 1
e[1] = 1
i = ne[1] = 0
第二个元素5
i = 0
e[0] = 5
i = ne[0] = -1
结束
java
后续如有时间,更新java纯链表结构
import java.io.*;
public class Main{
static int n;
static int N = 100010;
static int head;
static int[] e = new int[N], ne = new int[N];
static int idx;
public static void init(){
head = -1;
idx = 0;
}
public static void addToHead(int x){
e[idx] = x;
ne[idx] = head;
head = idx;
idx ++;
}
public static void remove(int k){
ne[k] = ne[ne[k]];
}
public static void insert(int k, int x){
e[idx] = x;
ne[idx] = ne[k];
ne[k] = idx;
idx ++;
}
public static void main(String[] args) throws IOException{
init();
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
while(n -- != 0){
int k, x;
String[] s = br.readLine().split(" ");
String opt = s[0];
if(opt.equals("H")){
x = Integer.parseInt(s[1]);
addToHead(x);
}else if(opt.equals("D")){
k = Integer.parseInt(s[1]);
if(k == 0) head = ne[head];
else remove(k - 1);
}else{
k = Integer.parseInt(s[1]);
x = Integer.parseInt(s[2]);
insert(k - 1, x);
}
}
for(int i = head; i != -1; i = ne[i]){
System.out.print(e[i] + " ");
}
}
}
python3
N = 100010
head = -1
e = [0] * N
ne = [0] * N
idx = 0
def addToHead(x):
global head, e, ne, idx
e[idx] = x
ne[idx] = head
head = idx
idx += 1
def remove(k):
global e, ne
ne[k] = ne[ne[k]]
def insert(k, x):
global e, ne, idx
e[idx] = x
ne[idx] = ne[k]
ne[k] = idx
idx += 1
def main():
global head, e, ne, idx
n = int(input())
while(n):
s = list(input().split(" "));
if(s[0] == 'H'):
x = int(s[1])
addToHead(x)
elif(s[0] == 'D'):
k = int(s[1])
if(k == 0): head = ne[head]
else: remove(k - 1)
else:
k = int(s[1])
x = int(s[2])
insert(k - 1, x)
n -= 1
i = head;
while(i != -1):
print(e[i], end=" ")
i = ne[i]
main();
c++
#include<iostream>
using namespace std;
const int N = 100010;
//head 表示头节点
//e[i] 表示节点i的值
//ne[i] 表示节点i的next指针(数组的索引值)
//idx 存储当前已经用到哪个点
int head, e[N], ne[N], idx;
//初始化
void init(){
head = -1; //头节点指针
idx = 0; //初始化待插入的元素
}
//将x插入到头节点
void add_to_head(int x){
e[idx] = x; //存储当前值
ne[idx] = head; //当前节点idx指向head指向的节点
head = idx; //head节点存储当前头节点的位置
idx ++;
}
//将x插入到下标是k的点后面
void add(int k, int x){
e[idx] = x; //存储当前值
ne[idx] = ne[k]; //当前节点指向k节点的下一个节点
ne[k] = idx; //节点k指向当前节点
idx ++;
}
//将下标是K的点后面的点删除
void remove(int k){
ne[k] = ne[ne[k]]; //k节点指向k的下一个节点的下一个节点
}
int main(){
int m;
cin >> m;
init();
while(m --){
int k, x;
char op;
cin >> op;
if(op == 'H'){
cin >> x;
//(1) “H x”,表示向链表头插入一个数x。
add_to_head(x);
}
else if(op == 'D'){
cin >> k;
//(2) “D k”,表示删除第k个插入的数后面的数(当k为0时,表示删除头结点)。
if(!k) head = ne[head]; //头节点 k = 0
else
remove(k - 1);
}
else{
cin >> k >> x;
//(3) “I k x”,表示在第k个插入的数后面插入一个数x(此操作中k均大于0)。
add(k - 1, x);
}
}
for(int i = head; i != -1; i = ne[i]) cout << e[i] <<" ";
cout << endl;
return 0;
}
大佬以后还会出python题解吗
我已经好久没写了,等有机会更新下
python版本wa了
啊?啥意思
$\color{red}{WA=WrongAnswer}$
我运行也没出问题。。。