前些天发现了一个巨牛的人工智能学习网站，通俗易懂，风趣幽默，忍不住分享一下给大家。点击跳转到网站
🌈C++专栏： 南桥谈C++
🌈C语言专栏： C语言学习系列
🌈Linux学习专栏： 南桥谈Linux
🌈数据结构学习专栏： 数据结构杂谈
🌈数据库学习专栏： 南桥谈MySQL
🌈Qt学习专栏： 南桥谈Qt
🌈菜鸡代码练习： 练习随想记录
🌈git学习： 南桥谈Git
链表常用技巧与操作
技巧
- 画图：直观且形象，便于理解
- 引入新的虚拟“头”结点：在算法题中，一般给的都是无头的单向链表，这种链表需要考虑很多的边界情况
- 便于处理边界情况
- 便于对链表操作
- 不要吝啬空间，大胆定义变量
- 快满双指针：判断链表是否有环、找链表中环的入口、找链表中倒数第n个节点
常见操作
- 创建新的节点
new - 尾插
- 头插
2.两数相加
2.两数相加
/*** 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* addTwoNumbers(ListNode* l1, ListNode* l2) {ListNode *cur1=l1,*cur2=l2;ListNode *res=new ListNode(0);ListNode *prev=res;int t=0;while(cur1||cur2||t){if(cur1){t+=cur1->val;cur1=cur1->next;}if(cur2){t+=cur2->val;cur2=cur2->next;}prev->next=new ListNode(t%10);prev=prev->next;t/=10;}prev=res->next;delete res;return prev;}
};
24.两两交换链表中的节点
24.两两交换链表中的节点
- 循环迭代（模拟）
- 定义变量，记录节点
- 实现两两节点交换即可
/*** 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* swapPairs(ListNode* head) {if(head==nullptr || head->next==nullptr) return head;ListNode *newhead=new ListNode(0);newhead->next=head;ListNode *prev=newhead,*cur=prev->next,*next=cur->next,*nnext=next->next;while(cur&&next){prev->next=next;next->next=cur;cur->next=nnext;prev=cur;cur=nnext;if(cur) next=cur->next;if(next) nnext=next->next;}cur=newhead->next;delete newhead;return cur;}
};
143.重排链表
143.重排链表
- 模拟
- 将链表一分为2，使用快慢指针找到分界点
- 合并两个链表即可
/*** 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:void reorderList(ListNode* head) {ListNode *slow=head,*fast=head;while(fast&&fast->next){slow=slow->next;fast=fast->next->next;}ListNode *head2=new ListNode(0);ListNode *cur=slow->next;slow->next=nullptr;while(cur){ListNode *next=cur->next;cur->next=head2->next;head2->next=cur;cur=next;}ListNode *ans=new ListNode(0);ListNode *anscur=ans,*cur1=head,*cur2=head2->next;while(cur1){anscur->next=cur1;cur1=cur1->next;anscur=anscur->next;if(cur2){anscur->next=cur2;cur2=cur2->next;anscur=anscur->next;}}delete head2;delete ans;}};
23.合并k个升序列表
23.合并k个升序列表
- 优先队列小根堆
- 先建立小根堆，链表的头结点加入到小根堆中
- 创建一个新的链表，将小根堆中的对顶加入的新链表中，并且将该堆顶元素的下一个节点加入到小根堆中
/*** 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:struct cmp{bool operator()(ListNode* l1,ListNode *l2){return l1->val > l2->val; //值较大的向下调整}};ListNode* mergeKLists(vector<ListNode*>& lists) {priority_queue<ListNode*,vector<ListNode*>,cmp> heap;//所有的头结点进入小根堆中for(auto l:lists){if(l) heap.push(l);}//合并ListNode *ans=new ListNode(0);ListNode *prev=ans;while(!heap.empty()){ListNode* t=heap.top();heap.pop();prev->next=t;prev=t;if(t->next) heap.push(t->next);}prev=ans->next;delete ans;return prev;}
};
25.K个一组翻转链表
25.K个一组翻转链表
- 模拟
- 先求出需要逆序多少组：n
- 重复n次，长度为k的链表逆序即可，直接使用头插法
/*** 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* reverseKGroup(ListNode* head, int k) {int n=0;ListNode *cur=head;while(cur){n++;cur=cur->next;}n/=k;ListNode *newhead=new ListNode(0);cur=head;ListNode *prev=newhead;for(int i=0;i<n;i++){ListNode *tmp=cur;for(int j=0;j<k;j++){ListNode *next=cur->next;cur->next=prev->next;prev->next=cur;cur=next;}prev=tmp;}prev->next=cur;cur=newhead->next;delete newhead;return cur;}
};
