代码随想录day3

203:移除链表元素：注意虚拟头节点的使用

ListNode* removeElements(ListNode* head, int val) {ListNode* result = new ListNode();result->next = head;ListNode* current = result;while(current != nullptr && current->next != nullptr){if(current->next->val == val){ListNode* tmp = current->next;current->next = tmp->next;delete tmp;}else{current = current->next;}}return result->next;}

707.设计链表：依然采用虚拟头节点方式

todo:学习双指针写法

class MyLinkedList {public:struct LinkedNode {int val;LinkedNode* next;LinkedNode(int val):val(val),next(nullptr){}};MyLinkedList() {prev = new LinkedNode(0);_size = 0;}int get(int index) {if(index < 0 || index >= _size){return -1;}LinkedNode* current = prev->next;//注意此处起始位置while(index--){current = current->next;}return current->val;}void addAtHead(int val) {LinkedNode* current = new LinkedNode(val);LinkedNode* tmp = prev->next;current->next = tmp;prev->next = current;_size++;}void addAtTail(int val) {LinkedNode* current = prev;while(current->next != nullptr){current = current->next;}LinkedNode* tail = new LinkedNode(val);current->next = tail;_size++;}void addAtIndex(int index, int val) {if(index > _size){return;}if(index < 0) index = 0;LinkedNode* current = prev;while(index--){current = current->next;}LinkedNode* node = new LinkedNode(val);node->next = current->next;current->next = node;_size++;}void deleteAtIndex(int index) {if(index < 0 || index > _size-1){return;}LinkedNode* current = prev;while(index--){current = current->next;}LinkedNode* tmp = current->next;current->next = tmp->next;delete tmp;_size--;}
private:int _size;LinkedNode* prev;
};

双链表写法：注意用过程变量来缓存节点，保持逻辑清晰

class MyLinkedList {public:struct DoubleLinkedNode {int val;DoubleLinkedNode* next;DoubleLinkedNode* prev;DoubleLinkedNode(int val):val(val),next(nullptr),prev(nullptr){}};MyLinkedList() {sentinel = new DoubleLinkedNode(0);sentinel->next = sentinel;sentinel->prev = sentinel;_size = 0;}int get(int index) {if (index > (_size - 1) || index < 0) { // 检查索引是否超出范围return -1; // 如果超出范围，返回-1}int num;int mid = _size >> 1; // 计算链表中部位置DoubleLinkedNode *curNode = sentinel; // 从哨兵节点开始if (index < mid) { // 如果索引小于中部位置，从前往后遍历for (int i = 0; i < index + 1; i++) {curNode = curNode->next; // 移动到目标节点}} else { // 如果索引大于等于中部位置，从后往前遍历for (int i = 0; i < _size - index; i++) {curNode = curNode->prev; // 移动到目标节点}}num = curNode->val; // 获取目标节点的值return num; // 返回节点的值}void addAtHead(int val) {DoubleLinkedNode* current = new DoubleLinkedNode(val);DoubleLinkedNode* next = sentinel->next;next->prev = current;current->prev = sentinel;current->next = next;sentinel->next = current;_size++;}void addAtTail(int val) {DoubleLinkedNode* current = new DoubleLinkedNode(val);DoubleLinkedNode* prev = sentinel->prev;prev->next = current;current->prev = prev;current->next = sentinel;sentinel->prev = current;_size++;}void addAtIndex(int index, int val) {if(index > _size){return;}DoubleLinkedNode* current = sentinel;while(index--){current = current->next;}DoubleLinkedNode* tmp = new DoubleLinkedNode(val);DoubleLinkedNode* next = current->next;tmp->next = next;tmp->prev = current;next->prev = tmp;current->next = tmp;_size++;}void deleteAtIndex(int index) {if(index < 0 || index >= _size){return;}DoubleLinkedNode* current = sentinel;while(index--){current = current->next;}DoubleLinkedNode* tmp = current->next;tmp->next->prev = current;current->next = tmp->next;delete(tmp);_size--;}
private:int _size;DoubleLinkedNode* sentinel;
};

206.反转链表：学习使用双链表法

ListNode* reverseList(ListNode* head) {ListNode* cur = head;ListNode* pre = nullptr;ListNode* tmp = head;while(cur){tmp = cur->next;cur->next = pre;pre = cur;cur = tmp;}return pre;}