文章目录
前言链表知识点
一、 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 here
ListNode* 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;
}
};
总结
链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
相关阅读
发表评论