代码随想录第三天

203 移除链表元素

了解链表申请节点，删除节点的基本操作。若不使用虚拟头结点，应该分头节点和中间节点两种情况。

/** * 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) { ListNode* star = new ListNode(0); star->next = head; ListNode* cur = star; 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 = star->next; delete star; return head; } };

707 设计链表

class MyLinkedList { public: struct ListNode { int val; // 节点存储的值 ListNode *next; // 指向下一个节点的指针 // 构造函数，方便创建节点 ListNode(int x) : val(x), next(nullptr) {} }; MyLinkedList() { star = new ListNode(0); size = 0; } int get(int index) { ListNode* flag = star->next; if(index < 0 || index >= size){ return -1; }else{ while(index){ flag = flag->next; index--; } return flag->val; } } void addAtHead(int val) { ListNode* newNode = new ListNode(val); newNode->next = star->next; star->next = newNode; size++; } void addAtTail(int val) { ListNode* newNode = new ListNode(val); ListNode* cur = star; while(cur->next != nullptr){ cur = cur->next; } cur->next = newNode; size++; } void addAtIndex(int index, int val) { ListNode* newNode = new ListNode(val); ListNode* flag = star; if(index >= 0 && index <= size){ while(index){ flag = flag->next; index--; } newNode->next = flag->next; flag->next = newNode; size++; } } void deleteAtIndex(int index) { ListNode* flag = star; if(index >= 0 && index < size){ while(index){ flag = flag->next; index--; } ListNode* cur = flag->next; flag->next = cur->next; delete cur; size--; } } private: int size; ListNode* star; }; /** * 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 反转链表

/** * 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* reverseList(ListNode* head) { ListNode* pre = NULL; ListNode* cur = head; while(cur){ ListNode* temp = cur->next; cur->next = pre; pre = cur; cur = temp; } return pre; } };