做网站排名赚钱吗,怎么看深圳网站页面设计,广州市建筑信息平台,抖音代运营公司怎么找客户文章目录 前言链表知识点 一、 92. 反转链表 II二、21. 合并两个有序链表总结 前言
一个本硕双非的小菜鸡#xff0c;备战24年秋招#xff0c;计划二刷完卡子哥的刷题计划#xff0c;加油#xff01; 二刷决定精刷了#xff0c;于是参加了卡子哥的刷题班#xff0c;训练… 文章目录 前言链表知识点 一、 92. 反转链表 II二、21. 合并两个有序链表总结 前言
一个本硕双非的小菜鸡备战24年秋招计划二刷完卡子哥的刷题计划加油 二刷决定精刷了于是参加了卡子哥的刷题班训练营为期60天我一定能坚持下去迎来两个月后的脱变的加油 推荐一手卡子哥的刷题网站感谢卡子哥。代码随想录
链表知识点
链表是一种通过指针串联在一起的线性结构每一个节点由两部分组成一个是数据域一个是指针域存放指向下一个节点的指针最后一个节点的指针域指向null空指针的意思。 链表的入口节点称为链表的头结点也就是head。 链表分为单链表、双链表、循环链表 链表在内存中储存不是连续分布的而是散乱分布在内存中的某地址上分配机制取决于操作系统的内存管理。
一、 92. 反转链表 II
92. 反转链表 II Note暴力与头插其中头插值得一看很有思考的一种方法。
class Solution {
private:void reverseLinkedList(ListNode *head) {// 也可以使用递归反转一个链表ListNode *pre nullptr;ListNode *cur head;while (cur ! nullptr) {ListNode *next cur-next;cur-next pre;pre cur;cur next;}}public:ListNode *reverseBetween(ListNode *head, int left, int right) {// 因为头节点有可能发生变化使用虚拟头节点可以避免复杂的分类讨论ListNode *dummyNode new ListNode(-1);dummyNode-next head;ListNode *pre dummyNode;// 第 1 步从虚拟头节点走 left - 1 步来到 left 节点的前一个节点// 建议写在 for 循环里语义清晰for (int i 0; i left - 1; i) {pre pre-next;}// 第 2 步从 pre 再走 right - left 1 步来到 right 节点ListNode *rightNode pre;for (int i 0; i right - left 1; i) {rightNode rightNode-next;}// 第 3 步切断出一个子链表截取链表ListNode *leftNode pre-next;ListNode *curr rightNode-next;// 注意切断链接pre-next nullptr;rightNode-next nullptr;// 第 4 步同第 206 题反转链表的子区间reverseLinkedList(leftNode);// 第 5 步接回到原来的链表中pre-next rightNode;leftNode-next curr;return dummyNode-next;}
};Note头插法画图思路不要乱。
/*** 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* reverseBetween(ListNode* head, int left, int right) {ListNode* dummyHead new ListNode(0);dummyHead-next head;ListNode* pre dummyHead;for (int i 1; i left; i)pre pre-next;ListNode* cur pre-next;ListNode* next NULL;for (int i 0; i right - left; i) {next cur-next;cur-next next-next;next-next pre-next;pre-next next;}return dummyHead-next;}
};二、21. 合并两个有序链表
21. 合并两个有序链表
Note这题还是递归简单一点
/*** struct ListNode {* int val;* struct ListNode *next;* ListNode(int x) : val(x), next(nullptr) {}* };*/
class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可** * param pHead1 ListNode类 * param pHead2 ListNode类 * return ListNode类*/ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {// write code hereListNode* dummyHead new ListNode(-1);ListNode* pre dummyHead;while (pHead1 ! nullptr pHead2 ! nullptr) {if (pHead1-val pHead2-val) {pre-next pHead1;pHead1 pHead1-next;} else {pre-next pHead2;pHead2 pHead2-next;}pre pre-next;}pre-next pHead1 nullptr ? pHead2 : pHead1;return dummyHead-next;}
};总结
链表是一种物理存储单元上非连续、非顺序的存储结构数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
