一键生成海报的网站,阳江最新通知今天,西安企业建站系统模板,上海展台搭建【ps】本篇有 5 道 leetcode OJ。 一、算法简介 链表是一种常见的线性数据结构#xff0c;是一种在物理结构上非连续、非顺序的存储结构#xff0c;其中的数据元素的逻辑顺序由其中的指针链接次序实现#xff0c;指针链接的每一个结构体都是一个节点。 链表的结构多种多样是一种在物理结构上非连续、非顺序的存储结构其中的数据元素的逻辑顺序由其中的指针链接次序实现指针链接的每一个结构体都是一个节点。 链表的结构多种多样有单向或双向、带头或不带头、循环或非循环之分。但实际中最常用的是以下两种组合
无头单向非循环链表或称单链表 带头双向循环链表或称双向链表 【Tips】链表的常用技巧 一定要画图引入一个虚拟的头节点利于处理边界情况、对链表进行各种操作。 不要吝啬空间大胆定义变量去使用尤其涉及到插入操作的时候。 快慢双指针可以对链表判环、找环的入口、找链表中倒数第 n 个节点。 【Tips】链表的常见操作 创建一个新节点尾插头插 二、相关例题 1两数相加
2. 两数相加 .1- 题目解析 要将两个链表的每个节点中的数相加并放在一个新的链表中那一定就要构建一个链表我们可以对这个新链表引入一个头节点然后直接遍历两个链表进行求和然后将结果构建出一个新节点尾插入头节点即可。 特别的我们单独定义一个变量 t既保存相加的结果又记录进位。 .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* newheadnew ListNode(0);ListNode*cur1l1,*cur2l2,*prevnewhead;int t0; //保存求和结果记录进位while(cur1||cur2||t){//取两个链表的节点进行求和if(cur1){tcur1-val;cur1cur1-next;}if(cur2){tcur2-val;cur2cur2-next;}prev-nextnew ListNode(t%10);//取结果的个位t/10; //取进位prevprev-next;}prevnewhead-next;delete newhead;return prev;}
}; 2两两交换链表中的节点
24. 两两交换链表中的节点 .1- 题目解析 以示例 1 为例。我们可以引入一个头节点并定义四个指针变量来表示不同的节点。 由此要实现题目要求的交换仅需交换 cur 和 next 指向的节点即可然后将这四个指针整体向后移动继续完成下次交换直到 cur 遇到了空节点说明此时整个链表都完成了交换。 .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* swapPairs(ListNode* head) {if(headnullptr||head-nextnullptr)return head; //处理边界情况ListNode* newheadnew ListNode(0);newhead-nexthead;ListNode* prevnewhead,*curnewhead-next;ListNode* nextcur-next,*nnextnext-next;while(cur next){//交换 cur 和 nextcur-nextnnext;next-nextcur;prev-nextnext;//继续遍历链表prevcur;curnnext;if(cur)nextcur-next;if(next)nnextnext-next;}curnewhead-next;delete newhead;return cur;}
}; 3重排链表
重排链表. - 力扣LeetCode .1- 题目解析 以示例 1 为例。如果将原始链表从中间一分为二将后半部分链表逆序然后将前半部分和后半部分的链表节点依此插入道一个新链表中前半部分先插入后半部分后插入就能得到题目要求的链表了。 我们可以用快慢双指针来找到链表的中间位置将后半部分的起始节点看作是慢指针的下一根节点然后用头插法来对后半部分的链表进行逆序操作这样无论原始链表的节点是单数还是复数都不会影响操作的正确性。 逆序完后半部分的链表之后依此将前后两部分的链表插入到一个新的头节点之后即可。 .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) {if(headnullptr||head-nextnullptr||head-next-nextnullptr)return;//找到原始链表的中间位置ListNode* fasthead,*slowhead;while(fastfast-next){slowslow-next;fastfast-next-next;}//头插法逆序后半部分ListNode* newheadnew ListNode(0);ListNode*curslow-next,*nextcur-next;slow-nextnullptr; //断开前后两个链表while(cur){nextcur-next;cur-nextnewhead-next;newhead-nextcur;curnext; }//合并两个链表ListNode* retnew ListNode(0);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;}
}; 4合并 K 个升序链表
23. 合并 K 个升序链表 .1- 题目解析 要合并 K 个升序链表可以先合并两个升序链表再继续两两合并剩下的链表。我们可以用优先级队列建小根堆排升序来优化这个过程将所有链表的头节点依此入队即可找到最小的那个节点只需将其尾插入一个新的头节点然后将后续的节点入队重复这个过程就可以完成 K 个升序链表的合并了。 另外先合并两个升序链表再继续两两合并剩下的链表也可以用归并的方式来解决。 .2- 代码编写
//法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 cmp{bool operator()(const ListNode* l1,const ListNode* l2){return l1-val l2-val;}};
public: ListNode* mergeKLists(vectorListNode* lists) {//创建一个小根堆priority_queueListNode*,vectorListNode*,cmp heap;//让所有链表的头节点进行小根堆for(auto l: lists) if(l)heap.push(l);//合并链表ListNode* retnew ListNode(0);ListNode* prevret;while(!heap.empty()){auto 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 mergeTowlist(l1,l2);}ListNode* mergeTowlist(ListNode* l1,ListNode* l2){if(l1nullptr)return l2;if(l2nullptr)return l1;ListNode head;ListNode* cur1l1,*cur2l2,*prevhead;head.nextnullptr;while(cur1cur2){if(cur1-valcur2-val){prev-nextcur1;prevcur1;cur1cur1-next;}else{prev-nextcur2;prevcur2;cur2cur2-next;}}if(cur1)prev-nextcur1;if(cur2)prev-nextcur2;return head.next;}
}; 5K 个一组翻转链表
25. K 个一组翻转链表 .1- 题目解析 .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* reverseKGroup(ListNode* head, int k) {//1.先求出需要逆序多少组int n0;ListNode* curhead;while(cur){curcur-next;n;}n/k;//2.重复n次长度为k的链表逆序ListNode* newHeadnew ListNode(0);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;}
};
