驻马店市住房和城乡建设局网站,音乐摄影网站建设宗旨,怎么做自己的淘宝网站,湖南企业竞价优化Day3 链表
链表也是一种很重要的数据结构#xff0c;链表的优势是空间不必连续#xff0c;分配比较自由#xff0c;缺点是不支持随机访问#xff0c;想要获取链表中间的某个元素#xff0c;必须要从头遍历。
LeetCode 203.移除链表元素【虚拟头结点】
移除链表中的某个…Day3 链表
链表也是一种很重要的数据结构链表的优势是空间不必连续分配比较自由缺点是不支持随机访问想要获取链表中间的某个元素必须要从头遍历。
LeetCode 203.移除链表元素【虚拟头结点】
移除链表中的某个元素很简单只需要把这个节点前一个节点的next指针指向这个节点后面一个元素即可。但是头结点是没有前一个节点的此时我们有两种做法一种是特判头结点如果头结点元素满条件则将头指针不断后移其余方法不变另一种方法是创造一个虚拟头结点让头结点在删除时的特性与其余节点一致而头结点的前驱就是我们创造的这个dummyhead。
解法1头结点特判
头结点特判有一点需要注意开头对头结点的判断要用while而不是if因为头结点之后如果存在连续相等的值在头结点删除后新的头结点仍满足条件则需要全部删除。
class Solution {
public:ListNode* removeElements(ListNode* head, int val) {while(head!NULL head-valval){ListNode* tmphead;headhead-next;delete tmp;}ListNode* curhead;while(cur!NULL cur-next!NULL){if(cur-next-valval){ListNode* tmpcur-next;cur-nextcur-next-next;delete tmp;}else curcur-next;}return head;}
};解法2虚拟头结点
这里是我的写法其实需要在中间的判断中用临时变量获取p-next然后delete掉清理内存这里没有写以后删除需要养成良好的习惯。
class Solution {
public:ListNode* removeElements(ListNode* head, int val) {ListNode* dummynew ListNode(0,head);ListNode* pdummy;while(p-next!NULL){if(p-next-valval){p-nextp-next-next;}else pp-next;}return dummy-next;}
};LeetCode 707.设计链表【链表基础】
最考验基本功的一集如果你仍然对链表操作有疑问那么请回到这一题它能解答你对所有链表基本操作的疑问。 这道题我在一开始做的时候用了数组模拟链表逃课AC了如果题目并没有强制要求用严格的链表结构实现有时候可以用数组模拟这样相当于用空间换了代码复杂度。
解法1数组模拟
class MyLinkedList {
public:int head,e[1010],ne[1010],idx,siz;MyLinkedList() {head-1;idx0;siz0;}int get(int index) {if(indexsiz || index0)return -1;int ihead;while(index--) ine[i];return e[i];}void addAtHead(int val) {e[idx]val;ne[idx]head;headidx;siz;}void addAtTail(int val) {addAtIndex(siz,val);}void addAtIndex(int index, int val) {if(indexsiz) return;if(index0){addAtHead(val);return;}int ihead;while(--index) ine[i];e[idx]val;ne[idx]ne[i];ne[i]idx;siz;}void deleteAtIndex(int index) {if(indexsiz || index0) return;if(index0){headne[head];siz--;return;}int ihead;while(--index) ine[i];ne[i]ne[ne[i]];siz--;}
};解法2链表结构
如果向上一题一样题目已经要求使用链表结构那就不能投机取巧了要把基本操作好好了解一下。
class MyLinkedList {
public:struct LinkedNode{int val;LinkedNode* next;LinkedNode(int val):val(val),next(nullptr){}};MyLinkedList() {dummyHeadnew LinkedNode(0);siz0; }int get(int index) {if(index(siz-1) || index0) return -1;LinkedNode* curdummyHead-next;while(index--) curcur-next;return cur-val;}void addAtHead(int val) {LinkedNode* newNodenew LinkedNode(val);newNode-nextdummyHead-next;dummyHead-nextnewNode;siz;}void addAtTail(int val) {LinkedNode* newNodenew LinkedNode(val);LinkedNode* curdummyHead;while(cur-next!NULL) curcur-next;cur-nextnewNode;siz;}void addAtIndex(int index, int val) {if(indexsiz) return;if(index0) index0;LinkedNode* newNodenew LinkedNode(val);LinkedNode* curdummyHead;while(index--) curcur-next;newNode-nextcur-next;cur-nextnewNode;siz;}void deleteAtIndex(int index) {if(indexsiz || index0) return;LinkedNode* curdummyHead;while(index--) curcur-next;LinkedNode* tmpcur-next;cur-nextcur-next-next;delete tmp;siz--;}private:int siz;LinkedNode* dummyHead;
};LeetCode 206.反转链表【双指针/递归】
反转链表也是一个非常经典的问题它要求我们每走一步就要改变两个节点之间next指针的位置这里有双指针法和递归法两种得好好研究一下。
解法1双指针
双指针解法是想法比较基础的解法就是用一前一后两个指针把后面的指针转到前面来。 细节第一步cur移动前要用tmp保存cur-next否则会丢失下一节点。 每次移动指针时先动pre再动cur否则两个指针会断连。
class Solution {
public:ListNode* reverseList(ListNode* head) {ListNode* curhead;ListNode* preNULL;ListNode* tmp;while(cur){tmpcur-next;cur-nextpre;precur;curtmp;}return pre;}
};解法2递归
递归解法的本质还是双指针算法只不过把双指针向前移动的过程转化为reverse函数中替换形参的过程不过代码确实很简洁当做思维扩展学了。
class Solution {
public:ListNode* reverse(ListNode* cur,ListNode* pre){if(curNULL) return pre;ListNode* tmpcur-next;cur-nextpre;return reverse(tmp,cur);}ListNode* reverseList(ListNode* head) {return reverse(head,NULL);}
};今日收获很多啊对链表的理解更深了。
