本文共 1693 字，大约阅读时间需要 5 分钟。

题目链接:

题目描述

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

(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

解题思路

题意:对单链表有三种操作，求出n次操作后的单链表。

Accepted Code:

/*  * @Author: lzyws739307453  * @Language: C++  */#include 
   
    using namespace std;const int MAXN = 100005;struct List {    int data, next;    List() {}    List(int data, int next) : data(data), next(next) {}}list_[MAXN];int cnt = 0, head = 0;void Insert_Head(int x) {    list_[++cnt] = List(x, list_[head].next);    list_[head].next = cnt;}void Delete(int k) {    if (!k)        head = list_[head].next;    else list_[k].next = list_[list_[k].next].next;}void Insert(int k, int x) {    list_[++cnt] = List(x, list_[k].next);    list_[k].next = cnt;}int main() {    char op;    int n, k, x;    scanf("%d", &n);    while (n--) {        scanf(" %c", &op);        if (op != 'I') {            if (op != 'D') {                scanf("%d", &x);                Insert_Head(x);            }            else {                scanf("%d", &k);                Delete(k);            }        }        else {            scanf("%d%d", &k, &x);            Insert(k, x);        }    }    int p = list_[head].next;    while (p) {        printf("%d ", list_[p].data);        p = list_[p].next;    }    printf("\n");    return 0;}
   

转载地址：http://oybtf.baihongyu.com/