new关键字
1.new是一个关键字，用于开辟空间，开辟的空间在堆上，而一般声明的变量存放在栈上；
2.new得到的是一段空间的首地址。所以一般需要用指针来存放这段地址
new int(10);//返回new出来这块内存的地址
int *p=new int(10);//用一个指针去接受这个地址
cout << p << endl;//返回内存空间地址00995B08
cout << *p << endl;//返回初始值10
delete 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;
}
else
p=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->next
cur->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();
}