203.移除链表元素
这个题是二刷了一开始这个思路就是利用虚拟头结点，但是中间很多小细节都考虑不到，例如初始化一个新的链表，循环条件的写法等
class Solution {
public:
struct ListNode{
int val;
ListNode *next;
ListNode(int x):val(x),next(NULL){};//定义构造函数
};
ListNode* removeElements(ListNode* head, int val) {
ListNode* dummy_head = new ListNode(0);//忘记初始化
dummy_head->next = head;
ListNode *cur;
cur = dummy_head;
//指向虚拟头节点，应该从下一个开始
while(cur->next!=NULL){
if(cur->next->val == val){
ListNode *tmp = cur->next;
cur->next = cur->next->next;
delete tmp;
}else{
cur = cur->next;
}
}
//循环完了要记得处理虚拟头结点
head = dummy_head->next;
delete dummy_head;
return head;
}
};
但是报错
Line 46: Char 49: error: cannot initialize a parameter of type
'ListNode ’ (aka 'Solution::ListNode ') with an lvalue of type
'ListNode ’ 46 | ListNode ret =
Solution().removeElements(param_1, param_2); return ret;
| ^~~~~~~ Line 18: Char 40: note: passing argument to parameter ‘head’ here 18 |
ListNode removeElements(ListNode head, int val) {
| ^
所以如果不定义构造函数使用默认构造函数的话，在初始化的时候就不能直接给变量赋值！注意卡哥说的在C++里面，要自己定义，leetcode里面默认的是可以直接赋值的。
因此代码将struct 链表定义删掉即可。
707.设计链表
问题：1.不知道初始化什么对象，以及里面要定义哪些值。2.index非法情况怎么具体在代码中体现。3.边界处理不到位，比如=size =0这些我还自己分开讨论，其实可以写在一起。
class MyLinkedList {
public:
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(NULL){};
};
MyLinkedList() {
// 初始化 MyLinkedList 对象
// 构造函数的名称与类的名称是完全相同的，并且不会返回任何类型，也不会返回
// void 构造函数可用于为某些成员变量设置初始值
dummy_head = new ListNode(0);
size = 0;
}
int get(int index) {
if (index >= (size) || index < 0) // =size-1是最后一个节点 =size就无效了
return -1;
ListNode* cur = dummy_head->next;
while (index--) {
cur = cur->next;
}
return cur->val;
}
void addAtHead(int val) {
ListNode* node = new ListNode(val);
node->next = dummy_head->next;
dummy_head->next = node;
size++;
}
void addAtTail(int val) {
ListNode* cur = dummy_head; // 卡哥没指向next，注意不能指向，因为有可能一开始是空的，就没有next一说
ListNode* node = new ListNode(val); // 这个要初始化为val不能是0
while (cur->next != NULL) {
cur = cur->next;
}
cur->next = node;
// node->next = NULL; //不用再指向空
size++;
}
void addAtIndex(int index, int val) {
if (index > size || index < 0) {
return;
}
ListNode* cur = dummy_head; // 不能next，因为要找插入节点的前一个节点
ListNode* node = new ListNode(val); // 这个要初始化为val不能是0
// 这个循环适用于index = 0/size
while (index--) {
cur = cur->next;
}
node->next = cur->next;
cur->next = node;
size++; // 忘记size++了
}
void deleteAtIndex(int index) {
if (index >= size || index < 0) { // 注意这里是=,=size就超过最后一个节点无效了
return;
}
ListNode* cur = dummy_head; // 不能next，因为要找delete节点的前一个节点
// 这个循环适用于index = 0/size
while (index--) {
cur = cur->next;
}
ListNode* tmp = cur->next;
cur->next = cur->next->next;
delete tmp;
// delete命令指示释放了tmp指针原本所指的那部分内存，
// 被delete后的指针tmp的值（地址）并非就是NULL，而是随机值。也就是被delete后，
// 如果不再加上一句tmp=nullptr,tmp会成为乱指的野指针
// 如果之后的程序不小心使用了tmp，会指向难以预想的内存空间
tmp = nullptr;
size--;//!!!!delete之后size--
}
private:
int size;
ListNode* dummy_head;
};
206.反转链表（双指针/递归）
- 双指针法
考虑用双指针法，但自己想的时候还是串联不起来思路。
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* cur = head;
ListNode* pre = nullptr;
while(cur!=nullptr){
ListNode* tmp = cur->next;//储存下一个值
cur->next = pre;
//pre cur ++
pre = cur;
cur = tmp;
}
return pre;//因为循环结束，cur=null是最后一个节点之后
}
};
- 递归
和双指针思路基本一致，需要定义一个reverse函数，一直递归调用，两个传递参数(pre,cur)，但是主函数只有一个head，怎么传递？那根据一开始的初始化来说，cur=head,pre=null，所以传递为reverse(head,null)。剩下的思路与双指针基本一致，所以很好写。
// 递归
class Solution {
public:
ListNode* reverse(ListNode* cur, ListNode* pre) { // 两个传递参数，但是主函数只有一个head，怎么传递？
if (cur == nullptr) {
return pre;
}
ListNode* tmp = cur->next; // 储存下一个值
cur->next = pre;
return reverse(tmp, cur);
}
ListNode* reverseList(ListNode* head) {
return reverse(head, nullptr);
}
};