代码随想录训练营day3:链表part1

理论

链表的增删操作时间复杂度O(1),查询时间复杂度O(n),因为要从头结点开始。使用场景和数据完全相反
链表的储存地址是不连续的。也和数组不同。

移除链表元素

利用虚拟头结点可以同意操作。不然删除头结点需要额外写。
记得返回的是虚拟头结点的next而不是虚拟头结点return dummyhead。哈哈哈

class Solution {
public:ListNode* removeElements(ListNode* head, int val) {ListNode* dummyhead = new ListNode(60);dummyhead->next=head;ListNode* cur=dummyhead;while(cur->next!=NULL){if(cur->next->val == val){ListNode* temp=cur->next;cur->next = cur->next->next;delete temp;}else{cur=cur->next;}}return dummyhead->next;}
};

设计链表

总是忘记判定插入或者删除的位置是否有效。

class MyLinkedList {
public:struct ListNode {int val;ListNode *next;ListNode(int val) : val(val), next(nullptr) {}};MyLinkedList() {dummyhead=new ListNode(0);size=0;}int get(int index) {if(index>size-1)return -1;ListNode* cur=dummyhead->next;for(int i=0;i<index;i++){cur=cur->next;}return cur->val;}void addAtHead(int val) {ListNode* head= new ListNode(val);head->next=dummyhead->next;dummyhead->next=head;size++;}void addAtTail(int val) {if(size==0) dummyhead->next=new ListNode(val);else{ListNode* cur=dummyhead->next;while(cur->next != NULL){cur=cur->next;}cur->next= new ListNode(val);}size++;}void addAtIndex(int index, int val) {if(index>size) return;ListNode* cur=dummyhead;for(int i=0;i<index;i++){cur=cur->next;}ListNode* temp=new ListNode(val);temp->next=cur->next;cur->next=temp;size++;}void deleteAtIndex(int index) {if(index>=size) return;ListNode* cur=dummyhead;for(int i=0;i<index;i++){cur=cur->next;};ListNode* temp=cur->next;cur->next=cur->next->next;delete temp;size--;}//void printLinkedList(){//}
private:int size;ListNode* dummyhead;
};

翻转链表

中间过程想到了用三个指针，双指针＋储存临时下一个的指针。
但是开头和结尾的处理过程没想出来。
直接让pre=head,这样的话还得加上head->next=nullptr才表示一条链表结束了。
所以让pre=null就不用特殊处理开头和结尾了。

    ListNode* reverseList(ListNode* head) {//if(head->next==nullptr) return nullptr;//ListNode* dummyhead= new ListNode(0);//dummyhead->next=head;//ListNode* pre=head;//ListNode* cur=pre->next;//ListNode* next=cur->next;//cur->next=pre;//head=reversal(cur,next);//return head;if(head==nullptr) return nullptr;ListNode* pre=nullptr;ListNode* cur=head;while(cur!=nullptr){ListNode* next=cur->next;cur->next=pre;pre=cur;cur=next;}return pre;}

快忘记递归怎么写啦，就是递归套递归。

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