列表

详情

AB9. 【模板】链表

描述

请你实现一个链表。
操作：
insert x y：将y加入链表，插入在第一个值为x的结点之前。若链表中不存在值为x的结点，则插入在链表末尾。保证x,y为int型整数。
delete x：删除链表中第一个值为x的结点。若不存在值为x的结点，则不删除。

输入描述

第一行输入一个整数n ()，表示操作次数。
接下来的n行，每行一个字符串，表示一个操作。保证操作是题目描述中的一种。

输出描述

输出一行，将链表中所有结点的值按顺序输出。若链表为空，输出"NULL"(不含引号)。

示例1

输入: 

5
insert 0 1
insert 0 3
insert 1 2
insert 3 4
delete 4

输出: 

2 1 3

原站题解

C++ 解法, 执行用时: 19ms, 内存消耗: 1192KB, 提交时间: 2022-06-05 

#include<iostream>
#include<unordered_map>
using namespace std;

struct Node{
    int val;
    Node *prev;
    Node *next;
    Node(int val){
        this->val = val;
        this->next = nullptr;
        this->prev = nullptr;
    }
};

int main(){
    Node *head = new Node(-1);
    Node *tail = new Node(-1);
    head->next = tail;
    tail->prev = head;
    unordered_map<int, Node*> mp;  // iterator,键值对，前面是值后面是地址
    int n;
    cin >> n;
    string s;
    int num1, num2;
    while(n--){
        cin >> s;
        if(s == "insert"){
            cin >> num1 >> num2;
            Node *node = new Node(num2);
            mp[num2] = node;
            Node *after;
            if(!mp.count(num1)){
                after = tail;
            } 
            else after = mp[num1];
            after->prev->next = node;
            node->prev = after->prev;
            node->next = after;
            after->prev = node;
        } 
        else {
            int num;
            cin >> num;
            if(mp.count(num)){
                Node *node = mp[num];
                node->prev->next = node->next;
                node->next->prev = node->prev;
                free(node);
                mp.erase(num);
            }
        }
    }
    if(head->next == tail){
        cout<< "NULL" << endl;
    } 
    else {
        while(head->next != tail){
            cout<< head->next->val << " ";
            head = head->next;
        }
        cout << endl;
    }
    return 0;
}

C++ 解法, 执行用时: 20ms, 内存消耗: 1204KB, 提交时间: 2022-05-04 

#include<iostream>
#include<unordered_map>
using namespace std;

struct Node{
    int val;
    Node *prev;
    Node *next;
    Node(int val){
        this->val = val;
        this->next = nullptr;
        this->prev = nullptr;
    }
};

int main(){
    Node *head = new Node(-1);
    Node *tail = new Node(-1);
    head->next = tail;
    tail->prev = head;
    unordered_map<int, Node*> mp;
    int n;
    cin >> n;
    string s;
    int num1, num2;
    while(n--){
        cin >> s;
        if(s == "insert"){
            cin >> num1 >> num2;
            Node *node = new Node(num2);
            mp[num2] = node;
            Node *after;
//             mp不存在num1时
            if(!mp.count(num1)){
                after = tail;
            } else {
                after = mp[num1];
            }
            after->prev->next = node;
            node->prev = after->prev;
            node->next = after;
            after->prev = node;
        } else {
            int num;
            cin >> num;
            if(mp.count(num)){
                Node *node = mp[num];
                node->prev->next = node->next;
                node->next->prev = node->prev;
                node = nullptr;
                mp.erase(num);
            }
        }
    }
    if(head->next == tail){
        cout<< "NULL" << endl;
    } else {
        while(head->next != tail){
            cout<< head->next->val << " ";
            head = head->next;
        }
        cout << endl;
    }
    return 0;
}

C++ 解法, 执行用时: 21ms, 内存消耗: 1204KB, 提交时间: 2022-03-25 

#include<iostream>
#include<unordered_map>
using namespace std;

struct Node{
    int val;
    Node* next;
    Node* prev;
    Node(int v):val(v), next(nullptr),prev(nullptr){}
};

int main(){
    Node* head = new Node(-1);
    Node* tail = new Node(-1);
    head->next =tail;
    tail->prev = head;
    unordered_map<int, Node*> map;
    int n ;
    cin >> n;
    string s;int num1, num2;
    while(n --){
        cin >> s;
        if(s == "insert"){
            cin >> num1 >> num2;
            Node* node = new Node(num2);
            map[num2] = node;
            Node* after;
            if(!map.count(num1)){
                after = tail;
            }else
                after = map[num1];
            after->prev->next = node;
            node->prev = after->prev;
            node->next = after;
            after->prev = node;
        }else{
            int num;
            cin >> num;
            if(map.count(num)){
                Node* node = map[num];
                node->prev->next = node->next;
                node->next->prev = node->prev;
                node = nullptr;
                map.erase(num);
            }
        }
    }
    if(head->next == tail)
        cout << "NULL"<<endl;
    else{
        while(head->next != tail){
            cout << head->next->val << " ";
            head = head->next;
        }
        cout <<endl;
    }
    
    return 0;
}

C++ 解法, 执行用时: 22ms, 内存消耗: 640KB, 提交时间: 2022-07-26 

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>

using namespace std;

vector<int> v;
vector<int>::iterator it;

int main(){
    int n;
    char ch[10];
    int x, y;
    scanf("%d", &n);
    while(n--){
        scanf("%s", ch);
        if(ch[0] == 'i'){
            scanf("%d%d", &x, &y);
            it = find(v.begin(), v.end(), x);
            v.insert(it, y);
        }
        else{
            scanf("%d", &x);
            it = find(v.begin(), v.end(), x);
            if(it != v.end()) v.erase(it);
        }
    }
    if(v.size() > 0)for(int i = 0; i < v.size(); i++) printf("%d ", v[i]);
    else printf("NULL");
}

C++ 解法, 执行用时: 24ms, 内存消耗: 536KB, 提交时间: 2022-06-02 

#include <bits/stdc++.h>
using namespace std;
vector<int> vec; //int类型的数据
vector<int>::iterator it; //int类型的迭代器，it是一个变量
int main(){
    int n;//操作数
    char str[6];//存放输入：insert/delete
    int x,y;
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%s",str);
        //insert
        if(str[0]=='i'){
            scanf("%d",&x);
            scanf("%d",&y);
            //cin>>x>>y>>endl;
            
            //将值x所在的位置返回给迭代器it。即把值x的地址返回给指针it
            it=find(vec.begin(),vec.end(),x);//若x不存在，迭代器it指向vec.end
            //将数据y插入链表
            vec.insert(it,y);         
        }
        //delete
        if(str[0]=='d'){
            scanf("%d",&x);
            it=find(vec.begin(),vec.end(),x);
            //因为end指向链表末尾的下一个元素，若x不存在删除end指向的元素，会越界访问报错
            if(it!=vec.end())
                vec.erase(it);
        } 
    }
    //链表不为空，输出链表中所有结点的值
    if(vec.size()>0){
        for(int i=0;i<vec.size();i++){
           // cout<<vec.at(i)<<" ";
            printf("%d ",vec[i]);
        }
    }
    else{
        printf("NULL");
    }
    
}




// #include<bits/stdc++.h>
// using namespace std;
// // const int N=1e+5;
// // int ans[N];
// vector <int> ans;
// int n;
// string s;
// int sizes;
// vector<int>::iterator it;//定义一个变量it
// //iterator是一种迭代器
// int main(){
//     cin>>n;
//     int x,y;
//     for(int i=0;i<n;++i){
//         cin>>s;
//         if(s=="insert"){
//             cin>>x>>y;//将y插入在第一值为x的结点之前，不存在则插在末尾
//             ans.insert(find(ans.begin(),ans.end(),x), y);//先从头到尾找x，在插入
//             //insert()用于在it前插入值为y的元素。
//             //find()用于在指定范围（ans的begin到end）查找和目标元素（x）值相等的第一个元素
//             //begin()返回向量头指针，指向第一个元素
//             //end()返回向量尾指针，指向向量最后一个元素的下一个位置
         
//         }  
//         else if(s=="delete"){//删除链表中第一个值为x的结点，若不存在值为x的结点，则不删除。
//             cin>>x;
//             it = find(ans.begin(),ans.end(),x);//先从头到尾找x，再赋值给it；
//             if(it != ans.end()){//it不等于ans[]最后一个指针
//                 ans.erase(it);
//                     //删除it处的一个字符
//             }
//         }
//     }
             
//     sizes = ans.size();//获取vecctor类型的长度。
//     if(sizes == 0){
//         cout << "NULL";
//     }
//     for(int i=0;i<sizes;++i){
//         cout << ans.at(i) << " ";//at()返回i处所指的数据，如果idx越界，显示越界。
//     }
//     return 0;
 
// }

上一题

© 2025 nowcoder.com