二、数据结构1：单链表模板题+算法模板（单链表）

Dear 丶 2023-10-09 23:58 21阅读 0赞

#### 文章目录 ####

*  算法模板
 *   *  单链表题目模板
 *  模板题
 *   *  单链表
     *   *  原题链接
         *  题目
         *  思路
         *  题解

## 算法模板 ##

### 单链表题目模板 ###

// head存储链表头，e[]存储节点的值，ne[]存储节点的next指针，idx表示当前用到了哪个节点
    int head, e[N], ne[N], idx;
    
    // 初始化
    void init()
    {
        
        head = -1;
        idx = 0;
    }
    
    // 在链表头插入一个数a
    void insert(int a)
    {
        
        e[idx] = a, ne[idx] = head, head = idx ++ ;
    }
    
    // 将头结点删除，需要保证头结点存在
    void remove()
    {
        
        head = ne[head];
    }

## 模板题 ##

### 单链表 ###

#### 原题链接 ####

[https://www.acwing.com/problem/content/828/][https_www.acwing.com_problem_content_828]

#### 题目 ####

826 . 单链表  
实现一个单链表，链表初始为空，支持三种操作：

向链表头插入一个数；  
删除第 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

#### 思路 ####

![在这里插入图片描述][454f555a9d124205ae81d48ba3b92bf3.png]  
![在这里插入图片描述][68c77f1eba7643bea608186690809734.png]  
![在这里插入图片描述][9bcec8d73ab44914aad6bd9a967300a9.png]  
![在这里插入图片描述][f304e80fd39a43298d5d25fd3667320d.png]

#### 题解 ####

#include <iostream>
    using namespace std;
    
    const int N = 1e5 + 10;
    int head,e[N],ne[N],idx;
    int n;
    // head 表示头结点的下标
    // e[i] 表示节点i的值
    // ne[i] 表示节点i的next指针是多少
    // idx 存储当前已经用到了哪个点
    
    // 初始化
    void init(){
        
    	head = -1;
    	idx = 0;
    }
    // 将x插到头结点
    void add_to_head(int x){
        
    	ne[idx] = head;
    	e[idx] = x;
    	head = idx;
    	idx ++;
    }
    // 将x插到下标是k的点后面
    void add(int k,int x){
        
    	ne[idx] = ne[k];
    	e[idx] = x;
    	ne[k] = idx; 
    	idx++;
    }
    // 将下标是k的点后面的点删掉
    void remove(int k){
        
    	ne[k] = ne[ne[k]];
    }
    int main(){
        
    	cin>>n;
    	
    	init();
    	
    	while(n--){
        
    		char c;
    		cin>>c; 
    		int k,x;
    		if(c == 'H'){
        
    			cin>>x;
    			add_to_head(x);
    		}
    		else if(c == 'I'){
        
    			cin>>k>>x;
    			add(k-1,x); // k从0开始 
    		}
    		else{
        
    			cin>>k;
    			if(!k) head = ne[head];
    			remove(k-1); // k从0开始 
    		}
    	}
    	for(int i=head;i!=-1;i=ne[i]) cout<<e[i]<<" ";
    
    	return 0;
    }

[https_www.acwing.com_problem_content_828]: https://www.acwing.com/problem/content/828/
[454f555a9d124205ae81d48ba3b92bf3.png]: https://img-blog.csdnimg.cn/454f555a9d124205ae81d48ba3b92bf3.png
[68c77f1eba7643bea608186690809734.png]: https://img-blog.csdnimg.cn/68c77f1eba7643bea608186690809734.png
[9bcec8d73ab44914aad6bd9a967300a9.png]: https://img-blog.csdnimg.cn/9bcec8d73ab44914aad6bd9a967300a9.png
[f304e80fd39a43298d5d25fd3667320d.png]: https://img-blog.csdnimg.cn/f304e80fd39a43298d5d25fd3667320d.png