题目描述
实现一个单链表,链表初始为空,支持三种操作:
向链表头插入一个数;
删除第 k 个插入的数后面的数;
在第 k 个插入的数后插入一个数。
现在要对该链表进行 M 次操作,进行完所有操作后,从头到尾输出整个链表。
注意:
题目中第 k 个插入的数并不是指当前链表的第 k 个数。例如操作过程中一共插入了
n个数,则按照插入的时间顺序,这 n 个数依次为:第 1 个插入的数,第 2 个插入的数,…第 n 个插入的数。
输入格式
第一行包含整数 M,表示操作次数。
接下来 M 行,每行包含一个操作命令,操作命令可能为以下几种:
H x,表示向链表头插入一个数 x。
D k,表示删除第 k 个插入的数后面的数(当 k 为 0 时,表示删除头结点)。
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
数组模拟单链表的优势
速度快。C++中new动态分配一个新节点的操作极慢,用new大概率TLE,故用数组模拟静态链表。
图示(重要)
三种插入方式:
删除:
参考自C语言中文网:
算法1(y总写法-数组模拟单链表)
#include<iostream>
using namespace std;
const int N=100010;
int idx,head,e[N],ne[N];
//idx:存储当前已经用到了哪个点
//e[N]:当前节点值
//ne[N]:下一节点的指针
void init()
{
idx=0;//初始为0
head=-1;//初始指向NULL
}
void add_to_head(int x)//头插法
{
e[idx]=x;//赋值
ne[idx]=head;//不是head=ne[head];
head=idx;//更新头结点
idx++;//idx被用过,移到下一位置
}
void add(int k,int x)//在k后插入
{
e[idx]=x;//结合图示即可理解
ne[idx]=ne[k];
ne[k]=idx++;
}
void remove(int k)//将k后的点删除
{
ne[k]=ne[ne[k]];//结合图示即可理解
}
int main()
{
init();//勿忘初始化
int m;
scanf("%d",&m);
while(m--)
{
int k,x;
char op;
// scanf("%c",&op);//scanf读字符时,会同时读入空格和回车,所以要特判一下空格和回车
cin>>op;//cin读字符,会自动将字符和回车过滤掉,所以不需要特判
if(op=='H')
{
cin>>x;// scanf("%d",&x);
add_to_head(x);
}
else if(op=='D')
{
cin>>k;// scanf("%d",&k);
if(!k) head=ne[head]; //特判,如果k=0,则删除头结点
remove(k-1);//k-1因为idx下标从0开始,因此第k个插入点的下标为k-1
}
else
{
cin>>k>>x;//scanf("%d %d",&k,&x);
add(k-1,x);
}
// cout<<op<<endl;// printf("%c",op);
}
for(int i=head;i!=-1;i=ne[i])//依次输出单链表
cout<<e[i]<<" ";//printf("%d",e[i]);
return 0;
}
算法2(java数组模拟链表)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
/**
* Created by Yolanda on 2021/5/13 21:18
*/
public class Main {
private static int N=100010;
private static int idx;
private static int head;
private static int[] e=new int[N];
private static int[] ne=new int[N];
static void init()
{
idx=0;
head=-1;
}
static void addToHead(int x)
{
e[idx]=x;
ne[idx]=head;
head=idx;
idx++;
}
static void addK(int k,int x)
{
e[idx]=x;
ne[idx]=ne[k];
ne[k]=idx++;
}
static void remove(int k)
{
ne[k]=ne[ne[k]];
}
public static void main(String[] args) throws IOException {
init();
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
int m=Integer.parseInt(br.readLine());
while(m-->0)
{
int x,k;
String[] a=br.readLine().split(" ");
String op=a[0];
if(op.equals("H"))
{
x = Integer.parseInt(a[1]);
addToHead(x);
}
else if(op.equals("D"))
{
k = Integer.parseInt(a[1]);
if(k==0) //注意此处的if-else不可类似C++式简写
{
head=ne[head];
}
else
{
remove(k-1);
}
}
else
{
k = Integer.parseInt(a[1]);
x = Integer.parseInt(a[2]);
addK(k-1,x);
}
}
for(int i=head;i!=-1;i=ne[i])
{
System.out.print(e[i]+" ");
}
}
}
算法3(LeetCode版传统java链表)
public class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
待更新......
算法4(C++纯链表结构)
#include<iostream>
#include<vector>
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode() : val(0), next(nullptr) {}
ListNode(int x, ListNode *next) : val(x), next(next) {}
};
int main()
{
ListNode* head=new ListNode;
int idx=0;
int m;
scanf("%d",&m);
vector<ListNode*> pos(m+1);
char c=getchar();
while(m--)
{
c=getchar();
int k,x;
if(c=='H')
{
cin>>x;
pos[idx]=new ListNode(x,head->next);
head->next=pos[idx++];
}
else if(c=='D')
{
cin>>k;
if(k==0)
head->next=head->next->next;
else if(pos[k-1]->next)
pos[k-1]->next=pos[k-1]->next->next;
}
else if(c=='I')
{
cin>>k>>x;
pos[idx]=new ListNode(x,nullptr);
pos[idx]->next=pos[k-1]->next;
pos[k-1]->next=pos[idx++];
}
getchar();
}
ListNode* p=head->next;
while(p)
{
cout<<p->val<<" ";
p=p->next;
}
return 0;
}
待更新......
算法5(python3)
N = 100010
head = -1
idx = 0
e = [0] * N
ne = [0] * N
def addToHead(x):
global head, e, ne, idx
e[idx] = x
ne[idx] = head
head = idx
idx += 1 # python没有i++
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
m = int(input())
while m:
a = list(input().split(" "))
if a[0] == 'H':
x = int(a[1])
addToHead(x)
elif a[0] == 'D':
k = int(a[1])
if k == 0:
head = ne[head]
else:
remove(k - 1)
else:
k = int(a[1])
x = int(a[2])
insert(k - 1, x)
m -= 1
i = head
while i != -1:
print(e[i], end=" ")
i = ne[i]
main()