网站开发全栈工程师技能图,建站公司费用,wordpress弱点,wordpress3.1目录 链表
1.常用技巧
1#xff09;画图#xff01;#xff01;#xff01; - 直观 形象 便于我们理解
2#xff09;引入虚拟“头”节点
1.便于处理边界条件
2.方便我们对链表进行操作
3.不要吝啬空间#xff0c;大胆定义变量
4.快慢双指针
1.判断链表是否…目录 链表
1.常用技巧
1画图 - 直观 形象 便于我们理解
2引入虚拟“头”节点
1.便于处理边界条件
2.方便我们对链表进行操作
3.不要吝啬空间大胆定义变量
4.快慢双指针
1.判断链表是否存在环
2.链表中的常用操作
1.创建一个新节点new
2.尾插
3.头插、
1. 两数相加medium
解析
1暴力
2优化
总结
2. 两两交换链表中的节点medium
解析
1暴力
2优化
总结
3. 重排链表medium
解析
模拟
第一步eg链表1-2-3-4-5
第二步
第三步
总结
4. 合并 K 个升序链表hard
解析
1暴力
2优化
1大小堆
2分治_归并
步骤
总结
5. K个⼀组翻转链表hard
解析
模拟
那么这里就要补充一个狠狠狠重要的只是点了三指针翻转链表
总结 链表
1.常用技巧 1画图 - 直观 形象 便于我们理解 2引入虚拟“头”节点 1.便于处理边界条件 2.方便我们对链表进行操作
要考虑很多的边界条件 3.不要吝啬空间大胆定义变量 4.快慢双指针
1.判断链表是否存在环 找到链表的入口 找到链表中倒数第n个节点 2.链表中的常用操作
1.创建一个新节点new
2.尾插 3.头插、
链表逆序用头插贼方便创建一个虚拟头节点进行遍历就可以逆序。 那么就进入例题吧
1. 两数相加medium
本题题意比较简单意思就是两个已经被反转的链表只要直接相加即可返回其相加后的链表这里要注意的就是进位操作。 解析
1暴力 我第一次做的时候确实是个小白什么都不会将所有数字都存入字符串内然后进行相加也要考虑进位或许将字符串转成int类型然后相加在to_string()转成字符串也可以但是这样太太太麻烦了。挺锻炼代码能力的有兴趣可以试试。 2优化 在两个链表上设置移动指针cur1和cur2然后设置进位next在while里面判断cur1 和 cur2 是否为空或者next是否存在进位但凡有一个满足条件就能继续相加添加到新链表的后端。这里注意的是链表不一样长那么就为了避免访问空指针的情况就要先判断cur1nullptr 和 cur2nullptr那么在这种情况下下如果为空就说明该链表已经遍历完0即可。 这里的进位需要注意的是先算出sum的总数然后添加到链表的是sum%10 的余数next表示进位就让sum/10证明存在进位的多少让下一次链表相加就在加上这个进位。说到底熟能生巧写多了自然就会了。 /*** 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* headnew ListNode();ListNode* lhead;int next0;while(l1||l2||next){int sum(l1?l1-val:0)(l2?l2-val:0)next;head-nextnew ListNode(sum%10);nextsum/10;if(l1) l1l1-next;if(l2) l2l2-next;headhead-next;}return l-next;}
};
总结
两个链表相加考虑进位其实是挺简单的链表操作可以直接在原链表上操作一定要想清楚再写代码这样负担很小不要直接上手就写但凡有一点思路不清楚就去画图 2. 两两交换链表中的节点medium
题意很简单两两交换链表间的节点比如【12】【34】【56】等等没有重复的节点那么就要考虑的是交换之后怎么有链接回原来的链表。 解析
1暴力 就是创建新的链表然后分奇偶添加但是这题不让创建新的链表。 2优化 这题实质就是模拟再原链表上进行交换那么只需要考虑的是原链表上交换的节点又要连接到原链表上就是要创建新的指针指向节点这样交换后就不会存在节点丢失的情况。 那么本题就是两个节点间的交换实质就是创建三个指针指向两个节点和交换后要链接的原链表上的节点。设置prevhead nowhead-nextnextnow-next;
这里专门设置了一个虚拟头节点是为了能让反转的链表重新连接回来其实这里也可以选择设置四个指针再指向next后面的一个节点。这样就可以无脑交换连接是不是很简单。这里就是要注意的是不要吝啬空间想创建指针就创建这样不会存在找不到原链表的情况。
两两交换完后那么这三个指针就再次往后移动让prev移动到被交换后的最后一个节点这样能保证prev再次充当虚拟头节点。
/*** 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* l) {ListNode* headnew ListNode();head-nextl;ListNode* prevhead;ListNode* nowhead-next;ListNode* nextnullptr;if(now) nextnow-next;ListNode* l1head;while(now!nullptrnext!nullptr){now-nextnext-next;prev-nextnext;next-nextnow;prevnow;nowprev-next;if(now)nextnow-next;}return l1-next;}
};
总结
关于在原链表内进行交换节点那么就要考虑三个指针的遍历指向链表上的节点然后进行无脑交换就OK这样不用担心创建的新链表不会链接不上的问题。 3. 重排链表medium
题意比较简单就是模拟问题重新排列这个链表 解析
模拟
第一步eg链表1-2-3-4-5
当都设指针prev和cur开始从第一个节点开始走让cur先手走两步prev走一步达到快慢指针的目的就能证明在cur走到链表尽头的时候prev正好在链表的中间节点。
那么此时就将链表分开形成两段链表。 eg:链表1-2-3-4-5 形成h1-1-2; h2-3-4-5; 第二步
翻转h2-3-4-5; h2-5-4-3;
我这里单独创建了一个翻转链表的函数还是比较简单的利用头插法新界一个头节点然后进行头插自然就反转了链表。 第三步 然后模拟h1 和 h2 交换链接的过程h-1-5-2-4-3,即可。 模拟两个链表相互交换的过程合并两个链表不用吝啬空间直接上去每个链表创建虚拟头节点然后进行交换相连然后再将三个指针往前移动即可。直到最后若存在没有被遍历完的节点直接连接到最后即可。 /*** 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* l) {//将l分成两段链表//快慢双指针记录ListNode* curl,*prevl;//prev停的位置就是链表的中点while(cur){curcur-next;if(cur) curcur-next;prevprev-next;}curl;while(cur-next!prev)curcur-next;cur-nextnullptr;//创建两个链表 h1,h2;ListNode* h1new ListNode(),*h2new ListNode();h1-nextl;h2-nextprev;ListNode* th1-next;while(t){coutt-val ;tt-next;}coutendl;ListNode* eh2-next;while(e){coute-val ;ee-next;} coutendl;//翻转链表(头插法)h2turnlist(h2); eh2-next;while(e){coute-val ;ee-next;} coutendl;//合并链表ListNode* r1h1-next,*r2nullptr; if(r1) r2r1-next;ListNode* r3h2-next,*r4nullptr; if(r3) r4r3-next;while(r1){r1-nextr3;r1r2;if(r2)r2r2-next;if(r3)r3-nextr1;r3r4;if(r4)r4r4-next;}}ListNode* turnlist(ListNode* h){ListNode* l1h-next;ListNode* lnew ListNode();ListNode* l2l;while(l1){ListNode* newnodenew ListNode(l1-val);newnode-nextl-next;l-nextnewnode;l1l1-next;}return l2;}};
总结
这题确实很锻炼代码的模拟能力十分推荐自己动手敲一遍。 4. 合并 K 个升序链表hard
题意很简单合并k个升序链表 解析
1暴力
创建一个链表然后两两进行合并每次两个链表都进行每个节点判断大小小的添加到链表上但是这样时间复杂度肯定很高并且很麻烦不过十分锻炼代码能力跟上题一样有时间可以试试。
2优化
1大小堆
其实能想到用堆优先级队列这题是真简单直接ac属于秒杀题了leetcode真是分不清有些中等题难的要死。
这题如果用优先级队列priority_queue(head-val),这里是大根堆如果不进行翻转priority_queue(head-val,vectorint,greaterint) 小根堆的话那么大根堆就进行头插这样就可以保证完全有序然后再插入新的链表完成一个完整的新链表的创建。 总结这里我之前用过set虽然能排序但会去重我就又去multiset不会去重但是每次删除的时候都会把所有相同的元素全都删除那么唯一满足条件的就是优先级队列了priority_queue。 /*** 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* mergeKLists(vectorListNode* lists) {priority_queueint q;int nlists.size();for(int i0;in;i){ListNode* curlists[i];while(cur){q.push(cur-val);curcur-next;}}ListNode* headnew ListNode();while(!q.empty()){ListNode* newnodenew ListNode(q.top());q.pop();newnode-nexthead-next;head-nextnewnode;}return head-next;}
};
2分治_归并
这种思想就是让数组一直细分一直细分到最后然后向上进行归并根上一个专题介绍的一模一样代码模板简直都是一模一样的一定要取尝试一下。
步骤 1.传送区间范围计算中间值 2.递归左右两边 3.一左一右合并两个链表 4.进行合并 /*** 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* mergeKLists(vectorListNode* lists) {return mergeSort(lists,0,lists.size()-1);}ListNode* mergeSort(vectorListNode* lists,int left,int right){if(leftright) return 0;if(leftright) return lists[left];//计算中间值int mid(leftright)1;//数组分两块【left,mid】 【mid1,right】ListNode* l1mergeSort(lists,left,mid);ListNode* l2mergeSort(lists,mid1,right);//合并两个链表return mergeTowlist(l1,l2);}ListNode* mergeTowlist(ListNode* l1,ListNode* l2){ListNode* headnew ListNode();ListNode* cur1l1,*cur2l2,*prevhead;while(cur1cur2){if(cur1-valcur2-val){prevprev-nextcur1;cur1cur1-next;}else {prevprev-nextcur2;cur2cur2-next;}}if(cur1) prev-nextcur1;if(cur2) prev-nextcur2;return head-next;}};
总结
本题有很多种办法这里两种优化的方法都推荐取试试真的写的很爽。 5. K个⼀组翻转链表hard
题意很简单理解就是不停的翻转k个节点 解析
模拟
其实这就是简单的模拟题思想挺简单的有点暴力内味hhh~
就是开头遍历节点个数然后计算count得出要经过多少次循环每次循环都进行k个节点的翻转就ok真的挺简单的那么主要就是进行链表的翻转然后再重新接回来。
开始我想到挺简单的创建新的链表然后进行链接就是采用头插法本来挺成功的就这里卡了我一个小时各种调试都没过最后还是去看题解了才发现用头插法连接到原链表上居然失效了只能再原链表上直接进行翻转。 那么这里就要补充一个狠狠狠重要的只是点了三指针翻转链表 三指针原链表反转 步骤 1.nodeprev-next 用node来记录当前节点的下一个节点这样在反转后能够找到下一个节点 2.prev-nexthead ; 让当前节点指向headhead就相当于一个标记节点 表示反转链表的头部 3.headprev; 每次反转成功后head都往后移动到prev的位置重新表示反转链表的头部 4.prev-nextnode; 然后进入下一轮反转要prev再次表示当前节点就重新指向node 那么每次传入区间内的链表的节点只要实现这三指针就可以完美的完成链表的原地翻转妈妈再也不用担心浪费空间了~ /*** 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* chang(ListNode* prev, ListNode* cur)
{ListNode* nodenullptr,*headnullptr;while(prev!cur){nodeprev-next;prev-nexthead;headprev;prevnode;}return head;
}ListNode* reverseKGroup(ListNode* l, int k) {ListNode* head new ListNode();head-next l;ListNode* cur head-next, * prev head;int n 0;while (prev-next) prev prev-next, n;int count n / k;prev head;while (count--){ListNode* next prev-next;for (int e 0; e k cur ! nullptr; e) cur cur-next;prev-next chang(prev-next, cur);next-next cur;prev next;}return head-next;
}
};
总结
这里最主要的就是关于在原链表上的直接翻转。哪怕用整整半天吃透我都觉得是值得的~ 总结一下吧~这次的链表专题我学到了很多希望也能帮到你
