自建网站视频教程,网站建设全部流程,怎样更新目录wordpress,婚纱摄影网页模板算法沉淀——链表 01.两数相加02.两两交换链表中的节点03.重排链表04.合并 K 个升序链表05.K个一组翻转链表 链表常用技巧 1、画图-直观形象、便于理解 2、引入虚拟头节点 3、要学会定义辅助节点#xff08;比如双向链表的节点插入#xff09; 4、快慢双指针… 算法沉淀——链表 01.两数相加02.两两交换链表中的节点03.重排链表04.合并 K 个升序链表05.K个一组翻转链表 链表常用技巧 1、画图-直观形象、便于理解 2、引入虚拟头节点 3、要学会定义辅助节点比如双向链表的节点插入 4、快慢双指针判断链表是否有环、找到环的入口、找链表中倒数第n个节点等 链表常用操作 1、创建新节点 2、头插比如逆序链表 3、尾插 01.两数相加
题目链接https://leetcode.cn/problems/add-two-numbers/
给你两个 非空 的链表表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的并且每个节点只能存储 一位 数字。
请你将两个数相加并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外这两个数都不会以 0 开头。
示例 1
输入l1 [2,4,3], l2 [5,6,4]
输出[7,0,8]
解释342 465 807.示例 2
输入l1 [0], l2 [0]
输出[0]示例 3
输入l1 [9,9,9,9,9,9,9], l2 [9,9,9,9]
输出[8,9,9,9,0,0,0,1]提示
每个链表中的节点数在范围 [1, 100] 内0 Node.val 9题目数据保证列表表示的数字不含前导零
思路
这里因为本身就是逆序的链表其实是方便我们进行计算的我们只需要一个临时变量来记录进位的值即可然后我们可以正常按照计算规则逐个相加直至链表结束即可。
/*** 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* cur1l1, *cur2 l2;ListNode* newheadnew ListNode();ListNode* prevnewhead;int t0;while(cur1||cur2||t){if(cur1){tcur1-val;cur1cur1-next;}if(cur2){tcur2-val;cur2cur2-next;}prev-nextnew ListNode(t%10);prevprev-next;t/10;}prevnewhead-next;delete newhead;return prev;}
};02.两两交换链表中的节点
题目链接https://leetcode.cn/problems/swap-nodes-in-pairs/
给你一个链表两两交换其中相邻的节点并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题即只能进行节点交换。
示例 1
输入head [1,2,3,4]
输出[2,1,4,3]示例 2
输入head []
输出[]示例 3
输入head [1]
输出[1] 提示
链表中节点的数目在范围 [0, 100] 内0 Node.val 100
思路
我们可以先创造一个头节点其次就是画图用原链表和交换后的链表进行对比找规律利用链表的结点指针来进行交换找出结束循环的条件即可。 代码
/*** 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||!head-next) return head;ListNode* newheadnew ListNode();newhead-nexthead;ListNode* prevnewhead,*curprev-next,*nextcur-next,*nnextnext-next;while(curnext){prev-nextnext;next-nextcur;cur-nextnnext;prevcur;curnnext;if(cur) nextnnext-next;if(next) nnextnext-next;}prevnewhead-next;delete newhead;return prev;}
};03.重排链表
题目链接https://leetcode.cn/problems/reorder-list/
给定一个单链表 L 的头节点 head 单链表 L 表示为
L0 → L1 → … → Ln - 1 → Ln请将其重新排列后变为
L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …不能只是单纯的改变节点内部的值而是需要实际的进行节点交换。
示例 1
输入head [1,2,3,4]
输出[1,4,2,3]示例 2
输入head [1,2,3,4,5]
输出[1,5,2,4,3] 提示
链表的长度范围为 [1, 5 * 104]1 node.val 1000
思路
我们画图发现可以先使用快慢指针的方式找到中间节点然后使用头插法将后半部分逆序再逐个拼接两段链表即可得到所需要的链表
代码
/*** 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) {if(!head||!head-next||!head-next-next) return;ListNode* slowhead,*fasthead;while(fastfast-next){slowslow-next;fastfast-next-next;}ListNode* newheadnew ListNode();ListNode* curslow-next;slow-nextnullptr;while(cur){ListNode* nextcur-next;cur-nextnewhead-next;newhead-nextcur;curnext;}ListNode* retnew ListNode();ListNode* prevret;ListNode* cur1head,*cur2newhead-next;while(cur1){prev-nextcur1;cur1cur1-next;prevprev-next;if(cur2){prev-nextcur2;cur2cur2-next;prevprev-next;}}delete newhead;delete ret;}
};04.合并 K 个升序链表
题目链接https://leetcode.cn/problems/merge-k-sorted-lists/
给你一个链表数组每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中返回合并后的链表。
示例 1
输入lists [[1,4,5],[1,3,4],[2,6]]
输出[1,1,2,3,4,4,5,6]
解释链表数组如下
[1-4-5,1-3-4,2-6
]
将它们合并到一个有序链表中得到。
1-1-2-3-4-4-5-6示例 2
输入lists []
输出[]示例 3
输入lists [[]]
输出[]提示
k lists.length0 k 10^40 lists[i].length 500-10^4 lists[i][j] 10^4lists[i] 按 升序 排列lists[i].length 的总和不超过 10^4
思路1
这里最简单也是比较高效的一种写法就是使用一个小根堆将这k个链表的头节点放进去逐个将堆顶的最小链表节点拼接再逐个入堆最后就可以将k个有序链表完成拼接
代码1
/*** 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 {struct comp{bool operator()(const ListNode* l1,const ListNode* l2){return l1-vall2-val;}};
public:ListNode* mergeKLists(vectorListNode* lists) {priority_queueListNode*,vectorListNode*,comp heap;for(auto li:lists) if(li) heap.push(li);ListNode* retnew ListNode();ListNode* prevret;while(!heap.empty()){ListNode* theap.top();heap.pop();prev-nextt;prevt;if(t-next) heap.push(t-next);}prevret-next;delete ret;return prev;}
};思路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* mergeKLists(vectorListNode* lists) {return merge(lists,0,lists.size()-1);}ListNode* merge(vectorListNode* lists,int left,int right){if(leftright) return nullptr;if(leftright) return lists[left];int mid(leftright)1;ListNode* l1merge(lists,left,mid);ListNode* l2merge(lists,mid1,right);return mergeTlist(l1,l2);}ListNode* mergeTlist(ListNode* l1,ListNode* l2){if(l1nullptr) return l2;if(l2nullptr) return l1;ListNode* headnew ListNode();ListNode* cur1l1,*cur2l2,*prevhead;head-nextnullptr;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;}
};05.K个一组翻转链表
题目链接https://leetcode.cn/problems/reverse-nodes-in-k-group/
给你链表的头节点 head 每 k 个节点一组进行翻转请你返回修改后的链表。
k 是一个正整数它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍那么请将最后剩余的节点保持原有顺序。
你不能只是单纯的改变节点内部的值而是需要实际进行节点交换。
示例 1
输入head [1,2,3,4,5], k 2
输出[2,1,4,3,5]示例 2
输入head [1,2,3,4,5], k 3
输出[3,2,1,4,5]提示
链表中的节点数目为 n1 k n 50000 Node.val 1000
思路
这里我们可以先计算要翻转的子链表个数也就是要反转的次数再使用头插法逐个翻转拼接即可
代码
/*** 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 n0;ListNode* curhead;while(cur){curcur-next;n;}n/k;ListNode* newheadnew ListNode();ListNode* prevnewhead;curhead;for(int i0;in;i){ListNode* tmpcur;for(int j0;jk;j){ListNode* nextcur-next;cur-nextprev-next;prev-nextcur;curnext;}prevtmp;}prev-nextcur;curnewhead-next;delete newhead;return cur;}
};
