算法——链表
链表
- 定义
- 分配空间
- 思想
- 题目
一般算法竞赛不会考链表，因为评判时只看结果，过程不看，完全可以用数组解题。一般是面试、机试时考察，会看你代码。
定义
-
在物理上不连续，在逻辑上连续，大小不固定
-
物理上必须牺牲空间性，增加指针域，指向逻辑连续的下⼀个元素
-
链式存储关心的是节点结构，顺序存储关心的是整体结构
- 数据域：存数据元素的区域
- 指针域：存储直接后继位置的区域
-
根据链表构造不同，分为:
- 单向链表、单向循环链表
- 双向链表、双向循环链表
单链表为例，链表节点一般由两部分构成，即数据域和指针域：
typedef struct node{typename data;//数据域node* next; //指针域
}
分配空间
malloc函数
malloc函数是C语言中stdlib.h头文件下用于申请动态内存的函数,其返回类型是申请的同变量类型的指针。
typename* p = (typename*)malloc(sizeof(typename));
以申请一个 int 型变量和一个node 型结构体变量为例
int* p = (int*)malloc(sizeof(int));node* p = (node*)malloc(sizeof(node));
new运算符
new是 C++中用来申请动态空间的运算符,其返回类型同样是申请的同变量类型的指针。
typename* p=new typename;
可以看到，new 的写法比 malloc要简洁许多，只需要“new+ 类型名”即可分配一块该类型的内存空间，并返回一个对应类型的指针。如果申请失败，则会启动C++异常机制处理而不是返回空指针 NULL。
- 内存泄漏
free函数是对应malloc函数的，delete 运算符是对应 new 运算符的。其使用方法非常简单，只需要在feel或delete的参数中填写需要释放的内存空间的指针变量即可
feel(p);
delete(p);
函数主要实现了两个效果:
- 释放指针变量p所指向的内存空间
- 将指针变量p指向空地址 NULL。
- 由此可以知道，在 函数执行之后，指针变量p本身并没有消失，只不过让它指向了空地址 NULL，但是它原指向的内存是确实被释放了的。
思想
- 结构特点:
- 单向链表的每个节点只包含一个指针域，这样每个节点只能找到一个指向后继节点
- 单向链表无法往回走，开弓没有回头箭，这在插入和删除时，是重要的思维定式，单向链表的。头非常重要，丢失了，就再也找不回来了
- 链表的插入思想:
- 假设要插入的位置是x，那么在找位置的时候，是找到x、x-1还是x+1的位置上，才能够进行插入操作
- 先处理新节点，再处理老节点，新节点可以有效备份老节点的内容
- 链表的删除思想:
- 在前一个节点删除后一个节点。
- 带头节点和不带头节点的结构
- 链表中第一个节点究竟是存储实际元素还是存储表的额外信息来区分。
- 不带头节点的插入操作
- 如果在第一个节点之前做插入操作，头指针要等于新插入节点，同时还要考虑表之前为空的时。候，表头指向了第一个元素这些情况
- 带头节点的插入操作
- 无论怎么插入操作，最终都有一个前节点，这样符合链表插入操作的模型，处理起来较容易
题目
https://leetcode.cn/problems/reverse-linked-list/
链表原地逆置
思路1:
若带头结点，先将头结点摘下。
然后从第一个结点开始，挨个摘下每一个结点，摘下后用头插法建立新的链表。
思路2:
双指针法定义两个指针: pre和 cur ;pre在前 cur 在后。
每次让 pre 的 next 指向 cur ，实现一次局部反转。
局部反转完成之后，pre和cur 同时往前移动一个位置。
循环上述过程，直至 pre到达链表尾部。(注意，在循环过程中，需要记录pre->next)
详细代码（包含输入释放）：
#include<iostream>
#include<stdlib.h>
using namespace std;typedef struct ListNode{int val;ListNode *next;
}ListNode;ListNode* reverseList(ListNode* head) {ListNode*p=nullptr;ListNode*q=head;ListNode*tmp;while(q){tmp=q->next;q->next=p;p=q;q=tmp;} return p;
}void FreeList(ListNode*& head){ListNode*tmp;while(head){tmp=head->next;delete(head);head=tmp;}
}int main(){int n;cin>>n;ListNode*l=nullptr;ListNode*r=nullptr;for(int i=0;i<n;i++){int val;cin>>val;ListNode*node=new ListNode;node->val=val;node->next=nullptr;if(i==0){l=node;r=node;}else{r->next=node;r=node;}}l=reverseList(l);//倒置链表 ListNode* s = l;while(s){//输出链表 cout<<s->val<<" ";s=s->next;}FreeList(l);//释放链表 if(l==nullptr){//检测释放情况 cout<<"ok";}else{cout<<"no";}return 0;
}
还有一个递归的方法：
- 递归：把传进来的节点指针指向前一个节点
- 递归出口：传进来的节点
head==nullptr||head==nullptr - 递归体：
- 递归调用，把
head之后的先反转 head->next->next=head;
- 递归调用，把
ListNode* reverseList(ListNode* head) {if(head==nullptr||head->next==nullptr){//递归出口 return head;} ListNode* p=reverseList(head->next);//碰底返回 head->next->next=head;head->next=nullptr;return p;
}
2,
https://leetcode.cn/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof
思路:快慢指针的思想。
我们将第一个指针 fast指向链表的第 k+1个节点，第二个指针 slow 指向链表的第一个节点，此时二者之间刚好间隔k个节点。此时两个指针同步向后走当 fast走到链表的尾部空节点时，则此时slow指针刚好指向链表的倒数第k个节点。
ListNode* trainingPlan(ListNode* head, int cnt) {//快慢指针ListNode* f=head;//快指针 ListNode* S=head;//慢指针 for(int i=1;i<=cnt;i++){//让f与l相差cnt f=head->next;head=head->next;} while(f){f=f->next;S=S->next;}return S;
}
https://leetcode.cn/problems/linked-list-cycle-ii/
思路:
快慢指针的思想。使用快慢指针，fast和slow。它们起始都位于链表的头部。随后，sow指针每次向后移动-个位置，而 fast 指针向后移动两个位置。
判环:
如果链表中存在环，则 fast指针最终将再次与 slow指针在环中相遇。
定位:
设链表中环外部分的长度为a。环长b+c，slow指针进入环后，又走了 b的距离与 fast相遇。此时，假设fast指针已经走完了环的n圈，它走过的总距离为:
a+n*(b+c)+b=a+(n+1)*b+n*c
任意时刻，fast指针走过的距离都为 slow指针的2倍:a+(n+1)*b+n*c=2(a+b),移项得a=c+(n-1)(b+c);
相遇点到入环点的距离加上n-1圈的环长，恰好等于从链表头部到入环点的距离a。因此，当发现 快慢指针相遇时，我们再额外使用一个指针p。起始，p指向链表头部;随后它和 slow 每次向后移动一个位置。最终，它们会在入环点相遇。
ListNode *detectCycle(ListNode *head) {ListNode *f=head;ListNode *s=head;while(f){s=s->next;if(f->next==nullptr){return nullptr;}f=f->next->next;if(s==f){ListNode *p=head;while(p!=s){p=p->next;s=s->next;}return p;}}return nullptr;}