代码随想录day3链表1

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();
}