代码随想录算法训练营Day.3| 移除链表元素 设计链表 反转链表

长沙出差ing，今天的核心是链表，一个比较基础且重要的数据结构。对C++的指针的使用，对象的创建，都比较考察，且重要。

203.移除链表元素

dummyNode虚拟头节点很重要，另外就是一个前后节点记录的问题。但是LeetCode不能free，日常还是要养成用完指针free的好习惯。

/*** 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* removeElements(ListNode* head, int val) {if(head == NULL) return head;ListNode *var = head;ListNode *dummy = new ListNode(-1,head);ListNode *pre = dummy;dummy->next = head;while(var->next != NULL){if(var->val == val){pre->next = var->next;// free(var);var = pre->next;}else{pre = var;var = pre->next;}}if(var->val == val){pre->next = NULL;// free(var);}return dummy->next;}
};

707.设计链表

经典的设计链表，注意C++指针和对象的使用，在判断时还会漏掉最后一个节点或第一个节点的问题。这里就贴一下我的丑代码：

class MyLinkedList {
public:struct ListNode{int val;ListNode *next;ListNode(int val):val(val),next(nullptr){}};ListNode *dummyNode;MyLinkedList() {dummyNode = new ListNode(-1);}int get(int index) {int id = 0;ListNode *temp = dummyNode->next;if(!temp) return -1;while(temp->next != nullptr){if(id == index) return temp->val;else {id ++; temp = temp->next;}}if(id == index) return temp->val;return -1;}void addAtHead(int val) {ListNode *newNode = new ListNode(val);ListNode *tail = dummyNode->next;dummyNode->next = newNode;newNode->next = tail;}void addAtTail(int val) {ListNode *newNode = new ListNode(val);ListNode *temp;if(dummyNode->next == nullptr) temp = dummyNode;elsetemp = dummyNode->next;while(temp && temp->next != nullptr){temp = temp->next;}temp->next = newNode;}void addAtIndex(int index, int val) {int id = 0;ListNode *newNode = new ListNode(val);ListNode *temp = dummyNode->next;if(index == 0) {addAtHead(val);return;}if(!temp) return;while(temp->next != nullptr){if(id+1 == index) {ListNode *tail = temp->next;temp->next = newNode;newNode->next = tail;return;}else {id ++; temp = temp->next;}}if(id+1 == index) {ListNode *tail = temp->next;temp->next = newNode;newNode->next = tail;return;}return;}void deleteAtIndex(int index) {int id = 0;ListNode *temp = dummyNode->next;if(index == 0){if(temp){ListNode *tail = temp->next;// free(temp->next);dummyNode->next = tail;}return;}while(temp->next != nullptr){if(id+1 == index) {ListNode *tail = temp->next->next;// free(temp->next);temp->next = tail;return;}else {id ++; temp = temp->next;}}return;}
};/*** Your MyLinkedList object will be instantiated and called as such:* MyLinkedList* obj = new MyLinkedList();* int param_1 = obj->get(index);* obj->addAtHead(val);* obj->addAtTail(val);* obj->addAtIndex(index,val);* obj->deleteAtIndex(index);*/

206.反转链表

经典的链表反转，注意前后指针的记录即可。

class Solution {
public:ListNode* reverseList(ListNode* head) {ListNode* temp; // 保存cur的下一个节点ListNode* cur = head;ListNode* pre = NULL;while(cur) {temp = cur->next;  // 保存一下 cur的下一个节点，因为接下来要改变cur->nextcur->next = pre; // 翻转操作// 更新pre 和 cur指针pre = cur;cur = temp;}return pre;}
};