芸志建站怎么建立网站,手把手教你做网站7,24小时最新国际新闻,做网站字体用什么格式理论
链表的增删操作时间复杂度O(1),查询时间复杂度O(n),因为要从头结点开始。使用场景和数据完全相反 链表的储存地址是不连续的。也和数组不同。
移除链表元素
利用虚拟头结点可以同意操作。不然删除头结点需要额外写。 记得返回的是虚拟头结点的next而不是虚拟头结点retu…理论
链表的增删操作时间复杂度O(1),查询时间复杂度O(n),因为要从头结点开始。使用场景和数据完全相反 链表的储存地址是不连续的。也和数组不同。
移除链表元素
利用虚拟头结点可以同意操作。不然删除头结点需要额外写。 记得返回的是虚拟头结点的next而不是虚拟头结点return dummyhead。哈哈哈
class Solution {
public:ListNode* removeElements(ListNode* head, int val) {ListNode* dummyhead new ListNode(60);dummyhead-nexthead;ListNode* curdummyhead;while(cur-next!NULL){if(cur-next-val val){ListNode* tempcur-next;cur-next cur-next-next;delete temp;}else{curcur-next;}}return dummyhead-next;}
};设计链表
总是忘记判定插入或者删除的位置是否有效。
class MyLinkedList {
public:struct ListNode {int val;ListNode *next;ListNode(int val) : val(val), next(nullptr) {}};MyLinkedList() {dummyheadnew ListNode(0);size0;}int get(int index) {if(indexsize-1)return -1;ListNode* curdummyhead-next;for(int i0;iindex;i){curcur-next;}return cur-val;}void addAtHead(int val) {ListNode* head new ListNode(val);head-nextdummyhead-next;dummyhead-nexthead;size;}void addAtTail(int val) {if(size0) dummyhead-nextnew ListNode(val);else{ListNode* curdummyhead-next;while(cur-next ! NULL){curcur-next;}cur-next new ListNode(val);}size;}void addAtIndex(int index, int val) {if(indexsize) return;ListNode* curdummyhead;for(int i0;iindex;i){curcur-next;}ListNode* tempnew ListNode(val);temp-nextcur-next;cur-nexttemp;size;}void deleteAtIndex(int index) {if(indexsize) return;ListNode* curdummyhead;for(int i0;iindex;i){curcur-next;};ListNode* tempcur-next;cur-nextcur-next-next;delete temp;size--;}//void printLinkedList(){//}
private:int size;ListNode* dummyhead;
};翻转链表
中间过程想到了用三个指针双指针储存临时下一个的指针。 但是开头和结尾的处理过程没想出来。 直接让prehead,这样的话还得加上head-nextnullptr才表示一条链表结束了。 所以让prenull就不用特殊处理开头和结尾了。 ListNode* reverseList(ListNode* head) {//if(head-nextnullptr) return nullptr;//ListNode* dummyhead new ListNode(0);//dummyhead-nexthead;//ListNode* prehead;//ListNode* curpre-next;//ListNode* nextcur-next;//cur-nextpre;//headreversal(cur,next);//return head;if(headnullptr) return nullptr;ListNode* prenullptr;ListNode* curhead;while(cur!nullptr){ListNode* nextcur-next;cur-nextpre;precur;curnext;}return pre;}快忘记递归怎么写啦就是递归套递归。
class Solution {
private:ListNode* reversal(ListNode* pre,ListNode* cur){if(curnullptr) return pre;ListNode* tempcur-next;cur-nextpre;return reversal(cur,temp);}
public:ListNode* reverseList(ListNode* head) {ListNode* prenullptr;ListNode* curhead;return reversal(pre,cur);}};
