new關鍵字

1.new是一個關鍵字，用于開辟空間，開辟的空間在堆上，而一般聲明的變量存放在棧上；

2.new得到的是一段空間的首地址。所以一般需要用指針來存放這段地址

new int(10);//返回new出來這塊內存的地址int *p=new int(10);//用一個指針去接受這個地址cout << p << endl;//返回內存空間地址00995B08cout << *p << endl;//返回初始值10delete p;

3.開辟的內存空間需要記得delete掉，否則會造成內存泄漏！

delete p的時候：首先調用這個對象的析構函數，然后釋放這個對象的空間。

靜態鏈表

題目鏈接

#include <iostream>
#include <cstdio>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include<list>
#include <set>
#include <ctime>
#include<unordered_map>
#include <bitset>
#include<random>
#include<regex>
#include <chrono>using namespace std;typedef long long ll;
#define pr pair<double,int>
#define tp tuple<int,int,int>
const int N = 2e6 + 7;
const int mod = 998244353;
ll a[N],s[N];
ll n, m, k;
ll e[N];
ll ne[N];
ll head,idx;
void init()
{head = 0;idx = 1;
}
void head_add(ll x)
{e[idx]=x,ne[idx]=head,head=idx++;
}
void add(ll k,ll x)
{e[idx]=x,ne[idx]=ne[k],ne[k]=idx++;
}
void remove(ll k)
{ne[k]=ne[ne[k]];
}
void solve()
{ll m;cin>>m;while(m--){char c;cin>>c;if(c=='H'){ll x;cin>>x;head_add(x);}else if(c=='D'){ll k;cin>>k;if(k==0) head=ne[head];else remove(k);}else if(c=='I'){ll k,x;cin>>k>>x;add(k,x);}}for(ll i=1;i<=idx;i++)cout<<e[i]<<" ";
}int main()
{cin.tie(0); cout.tie(0);ios::sync_with_stdio(false);//提高cin、cout的輸入輸出效率solve();
}

移除鏈表元素

題目鏈接
文章講解
視頻講解

AC

設置一個虛擬頭結點，這樣原鏈表的所有節點就都可以按照統一的方式進行移除了。

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* removeElements(ListNode* head, int val) {ListNode* fake=new ListNode(0);fake->next=head;ListNode* p = fake;while (p->next != NULL) {if(p->next->val==val){ListNode* tmp=p->next;p->next=p->next->next;delete tmp;}elsep=p->next;}return fake->next;}
};

靜態鏈表做法

#include <iostream>
#include <cstdio>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include<list>
#include <set>
#include <ctime>
#include<unordered_map>
#include <bitset>
#include<random>
#include<regex>
#include <chrono>using namespace std;typedef long long ll;
#define pr pair<double,int>
#define tp tuple<int,int,int>
const int N = 2e6 + 7;
const int mod = 998244353;
ll a[N],s[N];
ll n, m, k;
ll e[N];
ll ne[N];
ll head,idx;
void init()
{head = -1;idx = 0;
}
void head_add(ll x)
{e[idx]=x,ne[idx]=head,head=idx++;
}
void add(ll k,ll x)
{e[idx]=x,ne[idx]=ne[k],ne[k]=idx++;
}
void remove(ll k)
{if (head == -1) return;// 如果刪除的是頭節點if (e[head] == k){head = ne[head];return;}// 從 head 開始找前驅節點ll prev = head;while (ne[prev] != -1 && e[ne[prev]] != k){prev = ne[prev];}// 找到了要刪除的節點的前驅if (ne[prev] != -1){ne[prev] = ne[ne[prev]];}
}void solve()
{init();ll m,val;cin>>m>>val;for(int i=0;i<m;i++){ll x;cin>>x;if(i==0) head_add(x);else add(i-1,x);}for(ll i=head;i!=-1;i=ne[i]){if(e[i]==val){remove(val);}}for(ll i=head;i!=-1;i=ne[i]){cout<<e[i]<<" ";}
}int main()
{cin.tie(0); cout.tie(0);ios::sync_with_stdio(false);//提高cin、cout的輸入輸出效率solve();
}

707. 設計鏈表

題目鏈接
文章講解
視頻鏈接

AC

class MyLinkedList {
public:// 定義鏈表節點結構體struct LinkedNode {int val;LinkedNode* next;LinkedNode(int val):val(val), next(nullptr){}};// 初始化鏈表MyLinkedList() {_dummyHead = new LinkedNode(0); // 這里定義的頭結點 是一個虛擬頭結點，而不是真正的鏈表頭結點_size = 0;}// 獲取到第index個節點數值，如果index是非法數值直接返回-1， 注意index是從0開始的，第0個節點就是頭結點int get(int index) {if (index > (_size - 1) || index < 0) {return -1;}LinkedNode* cur = _dummyHead->next;while(index--){ // 如果--index 就會陷入死循環cur = cur->next;}return cur->val;}// 在鏈表最前面插入一個節點，插入完成后，新插入的節點為鏈表的新的頭結點void addAtHead(int val) {LinkedNode* newNode = new LinkedNode(val);newNode->next = _dummyHead->next;_dummyHead->next = newNode;_size++;}// 在鏈表最后面添加一個節點void addAtTail(int val) {LinkedNode* newNode = new LinkedNode(val);LinkedNode* cur = _dummyHead;while(cur->next != nullptr){cur = cur->next;}cur->next = newNode;_size++;}// 在第index個節點之前插入一個新節點，例如index為0，那么新插入的節點為鏈表的新頭節點。// 如果index 等于鏈表的長度，則說明是新插入的節點為鏈表的尾結點// 如果index大于鏈表的長度，則返回空// 如果index小于0，則在頭部插入節點void addAtIndex(int index, int val) {if(index > _size) return;if(index < 0) index = 0;        LinkedNode* newNode = new LinkedNode(val);LinkedNode* cur = _dummyHead;while(index--) {cur = cur->next;}newNode->next = cur->next;cur->next = newNode;_size++;}// 刪除第index個節點，如果index 大于等于鏈表的長度，直接return，注意index是從0開始的void deleteAtIndex(int index) {if (index >= _size || index < 0) {return;}LinkedNode* cur = _dummyHead;while(index--) {cur = cur ->next;}LinkedNode* tmp = cur->next;cur->next = cur->next->next;delete tmp;//delete命令指示釋放了tmp指針原本所指的那部分內存，//被delete后的指針tmp的值（地址）并非就是NULL，而是隨機值。也就是被delete后，//如果不再加上一句tmp=nullptr,tmp會成為亂指的野指針//如果之后的程序不小心使用了tmp，會指向難以預想的內存空間tmp=nullptr;_size--;}// 打印鏈表void printLinkedList() {LinkedNode* cur = _dummyHead;while (cur->next != nullptr) {cout << cur->next->val << " ";cur = cur->next;}cout << endl;}
private:int _size;LinkedNode* _dummyHead;};

206. 反轉鏈表

題目鏈接
文章講解
視頻講解

AC

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* reverseList(ListNode* head) {ListNode* temp; // 保存cur的下一個節點ListNode* cur = head;ListNode* pre = NULL;while(cur) {temp = cur->next;  // 保存一下 cur的下一個節點，因為接下來要改變cur->nextcur->next = pre; // 翻轉操作// 更新pre 和 cur指針pre = cur;cur = temp;}return pre;}
};

靜態鏈表

#include <iostream>
#include <cstdio>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include<list>
#include <set>
#include <ctime>
#include<unordered_map>
#include <bitset>
#include<random>
#include<regex>
#include <chrono>using namespace std;typedef long long ll;
#define pr pair<double,int>
#define tp tuple<int,int,int>
const int N = 2e6 + 7;
const int mod = 998244353;
ll a[N],s[N];
ll n, m, k;
ll e[N];
ll ne[N];
ll head,idx;
void init()
{head = -1;idx = 0;
}
void head_add(ll x)
{e[idx]=x,ne[idx]=head,head=idx++;
}
void add(ll k,ll x)
{e[idx]=x,ne[idx]=ne[k],ne[k]=idx++;
}
void reverse()
{ll pre=-1;ll p=head;while(p!=-1){ll tmp=ne[p];ne[p]=pre;pre=p;p=tmp;}head=pre;
}
void solve()
{init();ll m;cin>>m;for(int i=0;i<m;i++){ll x;cin>>x;if(i==0) head_add(x);else add(i-1,x);}reverse();for(ll i=head;i!=-1;i=ne[i]){cout<<e[i]<<" ";}
}int main()
{cin.tie(0); cout.tie(0);ios::sync_with_stdio(false);//提高cin、cout的輸入輸出效率solve();
}