- 第一题：自己做，return那里问了ai
- 第二题：自己做，但有很多bug，一个小bug问的ai
- 第三题：自己只想出了新建链表的方法，看了解析然后自己写的原地反转
移除链表元素
题目链接/文章讲解/视频讲解：：[https://programmercarl.com/0203.移除链表元素.html]
解法
很简单的链表题，不多说。但是return的时候容易踩坑，不能直接返回head，因为有可能head被删除了，应该返回虚拟头节点的next。
class Solution {
public:ListNode* removeElements(ListNode* head, int val) {ListNode* newhead = new ListNode();newhead->next = head;ListNode* p = head;ListNode* q = newhead;while(p != nullptr){if(p->val == val){q->next = p->next;ListNode* del = p;p = p->next;delete del;}else{p = p->next;q = q->next;}}return newhead->next;}
};
设计链表
题目链接/文章讲解/视频讲解：[https://programmercarl.com/0707.设计链表.html]
解法
链表的常规题，不难，但有些麻烦，很多地方的小细节要注意，比如索引是否减一、指针是否越界等，根据索引删减时要想清楚指针该移动多少。
class MyLinkedList {
public:MyLinkedList() {head = new ListNode();size = 0;}int get(int index) {ListNode* p = head;while(index >= 0){p = p->next;if(p == nullptr) return -1;index--;}return p->val;}void addAtHead(int val) {ListNode* node = new ListNode();node->val = val;node->next = head->next;head->next = node;size++;}void addAtTail(int val) {ListNode* node = new ListNode();node->val = val;ListNode* p = head;while(p->next != nullptr){p = p->next;}p->next = node;node->next = nullptr;size++;}void addAtIndex(int index, int val) {ListNode* node = new ListNode();node->val = val;if(index > size) return;else if(index == size){ListNode* p = head;while(p->next != nullptr){p = p->next;}p->next = node;node->next = nullptr;size++;}else{ListNode* p = head;while(index > 0){p = p->next;index--;}ListNode* q = p->next;p->next = node;node->next = q;size++;}}void deleteAtIndex(int index) {if(index > size - 1) return;else{ListNode* p = head;while(index > 0){p = p->next;index--;}ListNode* q = p->next;p->next = q->next;delete q;size--;}}
private:ListNode* head;int size;
};
反转链表
题目链接： [https://programmercarl.com/0206.翻转链表.html ]
解法
把一个元素的next指向前一个就行，但是需要记录前后的节点。
class Solution {
public:ListNode* reverseList(ListNode* head) {ListNode* newhead = new ListNode();newhead->next = head;ListNode* p = newhead;ListNode* q;newhead = newhead->next;if(head == nullptr) return head;while(head->next != nullptr){q = head->next;head->next = p;p = head;head = q;}head->next = p;newhead->next = nullptr;return head;}
};
第三天打卡，目前感觉比学校的算法设计与分析课简单多了，坚持！