康复训练part3

1.虚拟头结点203. 移除链表元素 - 力扣LeetCodeclass Solution { public: ListNode* removeElements(ListNode* head, int val) { int vval; ListNode*dummyheadnew ListNode(0); dummyhead-nexthead; headdummyhead; ListNode*curhead; while(cur-next!nullptr) { if(cur-next-valv) { ListNode*tmpcur-next; cur-nextcur-next-next; delete tmp; }else{ curcur-next; } } headdummyhead-next; delete dummyhead; return head; } };写的时候总是超时最后才发现是忘记写curcur-next了....这里要注意是否删除对应的cur结点位置变化707. 设计链表 - 力扣LeetCodeclass MyLinkedList { private: struct ListNode{ int val; ListNode*next; ListNode(int x0):val(x),next(nullptr){} }; ListNode*head; int size; public: MyLinkedList():head(nullptr),size(0) {} int get(int index) { if(index0||indexsize) { return -1; } ListNode*curhead; for(int i0;iindex;i) { curcur-next; } return cur-val; } void addAtHead(int val) { ListNode*newNodenew ListNode(val); newNode-nexthead; headnewNode; size; } void addAtTail(int val) { ListNode*dummyheadnew ListNode(0); dummyhead-nexthead; headdummyhead; ListNode*newNodenew ListNode(val); ListNode*curhead; for(int i0;isize;i) { curcur-next; } newNode-nextcur-next; cur-nextnewNode; headhead-next; delete dummyhead; size; } void addAtIndex(int index, int val) { if(indexsize||index0){ return; } ListNode*dummyheadnew ListNode(0); dummyhead-nexthead; headdummyhead; ListNode*newNodenew ListNode(val); ListNode*curhead; for(int i0;iindex;i) { curcur-next; } newNode-nextcur-next; cur-nextnewNode; headhead-next; delete dummyhead; size; } void deleteAtIndex(int index) { if(index0||indexsize) { return; } ListNode*dummyheadnew ListNode(0); dummyhead-nexthead; headdummyhead; ListNode*curhead; for(int i0;iindex;i) { curcur-next; } ListNode*tmpcur-next; cur-nexttmp-next; delete tmp; headhead-next; delete dummyhead; size--; } };206. 反转链表 - 力扣LeetCodeclass Solution { public: ListNode* reverseList(ListNode* head) { if(headnullptr){ return nullptr; } ListNode*dummyheadnew ListNode(0); dummyhead-nexthead; headdummyhead; ListNode*curhead-next; stackListNode*Nodestack; while(cur!NULL){ Nodestack.push(cur); curcur-next; } ListNode*cuhead; while(!Nodestack.empty()) { ListNode*tmNodestack.top(); Nodestack.pop(); cu-nexttm; cucu-next; } cu-nextnullptr; return head-next; } };19. 删除链表的倒数第 N 个结点 - 力扣LeetCodeclass Solution { public: ListNode* removeNthFromEnd(ListNode* head, int n) { ListNode*dummyheadnew ListNode(0); dummyhead-nexthead; headdummyhead; ListNode*fasthead; ListNode*slowhead; fastfast-next; while(n--fast!NULL) { fastfast-next; } while(fast!NULL) { fastfast-next; slowslow-next; } ListNode*tmpslow-next; slow-nextslow-next-next; delete tmp; return head-next; } };这里用虚拟头结点主要是因为想要避免为了得到删除节点的前一个节点而对删除节点为头结点时的单独讨论2.双指针206. 反转链表 - 力扣LeetCodeclass Solution { public: ListNode* reverseList(ListNode* head) { ListNode*temp; ListNode*prenullptr; ListNode*curhead; while(cur) { tempcur-next; cur-nextpre; precur; curtemp; } return pre; } };