专做户外装备测评视频网站,做阿里巴巴网站装修要多久,网站设计定位,北京学校网站建设公司目录 一、两数相加二、两两交换链表的节点三、重排链表四、合并k个升序链表五、k个一组翻转链表 一、两数相加
题目#xff1a;
思路#xff1a;
注意整数是逆序存储的#xff0c;结果要按照题目的要求用链表连接起来遍历l1的cur1#xff0c;遍历l2的cur2#xff0c;和… 目录 一、两数相加二、两两交换链表的节点三、重排链表四、合并k个升序链表五、k个一组翻转链表 一、两数相加
题目
思路
注意整数是逆序存储的结果要按照题目的要求用链表连接起来遍历l1的cur1遍历l2的cur2和一个整数t用来表示进位t等于1要进位t等于0不需要进位先固定好头节点newhead所以cur1和cur2指向的val先要运算。为什么要先固定好头节点因为方便后面尾插相加的结果为变量tmp如果10就取后面的数(%10)并且t1否则直接用相加后的tmp来构造节点的值t还是0进入循环条件只要cur1、cur2、t任意一个不为空(t不等于0)就能进入循环有节点就加节点的值没节点就用进位循环中每次的tmp要刷新为0cur1不为空tmpcur1-valcur1往后走cur2不为空tmpcur2-valcur2往后走t等于1说明有进位tmp1。如果tmp10tmp取后面的数t 1否则还是相加后的tmpt 0然后构造新节点val为tmp尾插循环后tail-next 记得置为空最好返回newhead
代码
class Solution {
public:ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {ListNode* cur1 l1;ListNode* cur2 l2;int t 0;// 进位int tmp cur1-val cur2-val;cur1 cur1-next;cur2 cur2-next;if(tmp 10){t 1;tmp % 10;}ListNode* newhead new ListNode(tmp);ListNode* tail newhead;while(cur1 || cur2 || t){tmp 0;if(cur1 ! nullptr) {tmp cur1-val;cur1 cur1-next;}if(cur2 ! nullptr) {tmp cur2-val;cur2 cur2-next;}if(t) tmp t;if(tmp 10){t 1;tmp % 10;} else t 0;ListNode* newnode new ListNode(tmp);tail-next newnode;tail tail-next;}tail-next nullptr;return newhead;}
};二、两两交换链表的节点
题目 解法一 交换值能过 思路
链表为空返回空链表只有一个节点返回该链表链表大于1个节点prev指向第一个节点cur指向第二个节点循环为cur不为空进入循环cur和prev的节点值交换然后prev指向cur的下一个节点如果prev不为空cur指向prev的下一个节点(相当于走了两步)否则直接跳出循环然后原来的链表
代码
class Solution {
public:ListNode* swapPairs(ListNode* head) {if(head nullptr) return nullptr;if(head-next nullptr) return head;ListNode* cur head-next;ListNode* prev head;while(cur){int t cur-val;cur-val prev-val;prev-val t;prev cur-next;if(prev nullptr) break;cur prev-next;}return head;}
};解法二 交换节点 思路
如果为空链表或者链表只有一个节点直接返回head定义一个哨兵位头节点方便后续连接操作定义4个指针 注意连接顺序和可能为空的情况让head重新指向修改后的tmp的next销毁tmp返回head
代码
class Solution {
public:ListNode* swapPairs(ListNode* head) {if(head nullptr || head-next nullptr) return head;ListNode* tmp new ListNode(0);tmp-next head;ListNode* prev tmp;ListNode* cur head;ListNode* next cur-next;ListNode* 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;}head tmp-next;//delete tmp;return head;}
};三、重排链表
题目 思路
找到中间节点中间节点之后逆序然后如图先h1插入节点再h2插入节点如果链表的节点只有一个还是原来的链表找到中间节点——快慢双指针法链表逆序——头插法定义newhead为head先固定第一个节点。h1为中间节点后逆序的链表h2为head的下一个节点h1不为空尾插h1的节点h2不为slow因为slow指向的是中间节点的位置尾插h2的节点循环结束tail-next等于空headnewhead即还原head
代码
class Solution {
public:void reorderList(ListNode* head) {if(head-next nullptr) head head;else {ListNode* slow head;ListNode* fast head;while(fast fast-next){slow slow-next;fast fast-next-next;} ListNode* mid slow;ListNode* h1 nullptr;while(mid){ListNode* next mid-next;mid-next h1;h1 mid;mid next;}ListNode* h2 head-next;ListNode* newhead head;ListNode* tail newhead;while(h1){tail-next h1;tail tail-next;h1 h1-next;if(h2 ! slow){tail-next h2;tail tail-next;h2 h2-next;}}tail-next nullptr;head newhead;}}
};四、合并k个升序链表
题目 思路 小堆所有的链表的节点放入小堆然后取顶部依次尾插注意要考虑链表的某个节点可能为空的情况
代码
class Solution {
public:ListNode* mergeKLists(vectorListNode* lists) {priority_queueint, vectorint, greaterint pq;// 小堆ListNode* newhead nullptr;ListNode* tail nullptr;// k * n500(节点数)for(auto l : lists){if(l){ListNode* cur l;while(cur){pq.push(cur-val);cur cur-next;}}}// log(n*k) log(k)while(!pq.empty()){int t pq.top();ListNode* newnode new ListNode(t);if(tail nullptr){tail newhead newnode;}else {tail-next newnode;tail tail-next;}pq.pop();}return newhead;}
};五、k个一组翻转链表
题目
思路
两层循环外面是翻转的组的个数里面的一组的节点数头插法先用哨兵位节点newhead固定然后接下来每组的节点翻转后尾插到新的节点后面刚开始是哨兵位节点后面是上一组第一个头插的节点最后返回newhead的下一个节点记得循环哨兵位节点
代码
class Solution {
public:ListNode* reverseKGroup(ListNode* head, int k) {ListNode* newhead new ListNode(0);// 哨兵位节点先固定方便后面连接ListNode* tail newhead;// 方便找尾int n 0;// 节点数ListNode* cur head;// 遍历链表while(cur){n;cur cur-next;}n / k;// 翻转的组的个数int y k;// 为了还原原来的k值// cur head;// 回到第一个节点while(n--)// 循环组数{ListNode* tmphead nullptr;// 临时的头指针// 头插法while(k--)// 循环要翻转(头插)的节点数{ListNode* next cur-next;cur-next tmphead;tmphead cur;cur next;}k y;// 还原ktail-next tmphead;// 连接翻转的后一组子链表// 找到尾节点方便下次尾插新的一组子链表while(tail-next){tail tail-next;}}tail-next cur;// 尾插剩余的节点while(tail-next){tail tail-next;}tail-next nullptr;// ListNode* ret newhead-next;// 要返回的链表delete newhead;//return ret;}
};
