单链表（Java每日一题）

青旅半醒 2024-03-30 11:09 46阅读 0赞

## 单链表 ##

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

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

#include<iostream>
    
    using namespace std;
    
    const int N = 100010;
    // head 表示头节点
    // e[i] 表示结点i的值
    // ne[i] 表示结点i的next指针是多少
    // idx 存储当前已经用到了的那个点
    // 在这里面要记住的是idx 和 ne[]都是指针
    
    int head, e[N], ne[N], idx;
    
    // 初始化
    void init()
    {
        
    	head = -1;
    	idx = 0;
    }
    
    void add_to_head(int x)
    {
        
    	e[idx] = x;
    	ne[idx] = head;
    	head = idx;
    	idx++;
    }
    
    void add(int k, int x)
    {
        
    	e[idx] = x;  // e[idx]是一个新的结点
    	ne[idx] = ne[k];
    	ne[k] = idx;
    	idx++;
    }
    
    void remove(int k)
    {
        
    	if (k == -1) head = ne[head];
    	else ne[k] = ne[ne[k]];
    }
    
    int main()
    {
        
    	int m;
    	cin >> m;
    	init();
    
    	while (m--)
    	{
        
    		int k, x;
    		char op;
    		cin >> op;
    		if (op == 'H')
    		{
        
    			cin >> x;
    			add_to_head(x);
    		}
    		else if (op == 'D')
    		{
        
    			cin >> k;
    			remove(k - 1);
    		}
    		else
    		{
        
    			cin >> k >> x;
    			add(k - 1, x);
    		}
    	}
    	for (int i = head; i != -1; i = ne[i]) cout << e[i] << ' ';
    	cout << endl;
    	return 0;
    }

### Java ###

import java.io.*;
    
    public class Main
    {
        
        static int n;
        static int k, x;
        static int head;
        static int idx;
        static int N = 100010;
        static int[] e = new int[N], ne = new int[N];
        
        public static void init()
        {
        
            idx = 0;
            head = -1;
        }
        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 reader = new BufferedReader(new InputStreamReader(System.in));
            n = Integer.parseInt(reader.readLine());
            while(n -- != 0)
            {
        
                String [] s = reader.readLine().split(" ");
                if (s[0].equals("H"))
                {
        
                    x = Integer.parseInt(s[1]);
                    addToHead(x);
                }
                else if (s[0].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] + " ");
            }
        }
    }