算法二刷day3

203.移除链表元素

class Solution {
public:ListNode* removeElements(ListNode* head, int val) {ListNode *dummyHead = new ListNode(0);dummyHead->next = head;ListNode *cur = dummyHead;while (cur->next != nullptr) {if (cur->next->val == val) {ListNode *tmp = cur->next;cur->next = cur->next->next;delete tmp;}else {cur = cur->next;}}return dummyHead->next;}
};

707.设计链表

class MyLinkedList {
public:struct LinkedNode {int val;LinkedNode* next;LinkedNode(int val) : val(val), next(nullptr){}};MyLinkedList() {_dummyHead = new LinkedNode(0);_size = 0;}int get(int index) {if ((_size - 1) < index || index < 0) return -1; //先排除下标无效情况LinkedNode *cur = _dummyHead->next;while (index--) {cur = cur->next;}return cur->val;}void addAtHead(int val) {LinkedNode *newNode = new LinkedNode(val);newNode->next = _dummyHead->next;_dummyHead->next = newNode;++_size;} // 这里不要忘记size++void addAtTail(int val) {LinkedNode *cur = _dummyHead;while (cur->next != nullptr) {cur = cur->next;}LinkedNode *newNode = new LinkedNode(val);cur->next = newNode;++_size;}void addAtIndex(int index, int val) {if (index > _size) return;if(index < 0) index = 0;LinkedNode *cur = _dummyHead;while (index--) {cur = cur->next;}LinkedNode *newNode = new LinkedNode(val);newNode->next = cur->next;cur->next = newNode;_size++;}void deleteAtIndex(int index) {if (index >= _size || index < 0) {return;}LinkedNode *cur = _dummyHead;while (index--) {cur = cur->next;}LinkedNode* tmp = cur->next;cur->next = cur->next->next;delete tmp;tmp=nullptr;_size--;}void printLinkedList() {LinkedNode *cur = _dummyHead;while (cur->next != nullptr) {cout << cur->next->val << " ";cur = cur->next;}cout << endl;}private:int _size;LinkedNode *_dummyHead;};

206.反转链表

class Solution {
public:ListNode* reverse(ListNode* pre, ListNode* cur) {if (cur == nullptr) return pre;ListNode* tmp = cur->next;cur->next = pre;return reverse(cur, tmp);}ListNode* reverseList(ListNode* head) {return reverse(nullptr, head);}
};