如何申请建设网站首页,个人网页设计作品纯html,下载百度app最新版并安装,集团网站建设报价链表是一个用指针串联起来的线性结构#xff0c;每个结点由数据域和指针域构成#xff0c;指针域存放的是指向下一个节点的指针#xff0c;最后一个节点指向NULL#xff0c;第一个结点称为头节点head。 常见的链表有单链表、双向链表、循环链表。双向链表就是多了一个pre指…链表是一个用指针串联起来的线性结构每个结点由数据域和指针域构成指针域存放的是指向下一个节点的指针最后一个节点指向NULL第一个结点称为头节点head。 常见的链表有单链表、双向链表、循环链表。双向链表就是多了一个pre指针头节点的pre指向NULL。循环链表就是尾节点的next指向了头节点可以用来解决约瑟夫问题。 链表内存为节点间不连续节点内连续。适用于解决数据长度不固定不经常查找经常增删的问题。 要学会自己定义struct ListNode并且要知道构造函数自己写完怎么用使用ListNode *node new ListNode(3)这样就可以new一个ListNode出来让node指向了。 1.移除元素 Leetcode203. 分为虚拟节点和不使用虚拟节点 在这一题里我终于体会到了tmpnullptr的用处。 代码随想录里明明只使用了delete tmp但是我没有用tmp nullptr 还是报了内存的错误下面这样写才通过但是看起来明明不对。 /*** 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) {// 2. 使用虚拟头节点while(head!nullptr head-val val){ListNode* tmp head;//内存~head head-next;delete tmp;//内存~}ListNode* cur head;while(cur ! nullptr cur-next ! nullptr){if(cur-next-val val){ListNode* tmp cur-next;//~cur-next cur-next-next;delete tmp;//~}elsecur cur-next;}return head; }
}; /*** 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) {// 2. 使用虚拟头节点ListNode *dummynode new ListNode();dummynode-next head;ListNode *cur dummynode;while(cur ! nullptr cur-next ! nullptr){if(cur-next-val val){ListNode* tmp cur-next;//考虑一下内存不考虑也没事只是大一些cur-next cur-next-next;delete tmp;//~同上}elsecur cur-next;}return dummynode-next; }
}; 这里要注意我的虚拟头节点也是一个指针类型的因为我要使用到dummynode-next这种操作仅仅是指向虚拟头结点的一个指针而已。我一开始用的是ListNode dummynode new ListNode()这是不对的。 [注意]通常情况下在执行了 delete 操作之后将指针置为 nullptr 是不必要的因为你不应该在删除后继续使用已经释放的内存。这不是内存管理的原则之一。这里delete之前要暂存一下删的东西地址不然不知道删啥。 2.设计链表20230828 本题给了ListNode的节点定义需要写MyLinkedList中的构造函数、get、addAtHead、addAtTail、addAtIndex、deleteAtIndex。 需要注意的是第一写错了什么东西--。我本来是index--误写成tmp--找了半天也没发现哪里错。 第二个写错的是这里 这里写错了其实index0也可以删就是把头节点删掉。这里错误导致我有三个用例不通过都是delete头节点的。改成0就行了。 这一题熟悉了链表的操作并且深刻体会了虚拟头节点的妙用。 3.反转链表LCR024 20230829 双指针法清晰易懂 /*** 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 nullptr;ListNode *cur head;while(cur){ListNode *tmp cur - next; cur - next pre;pre cur;cur tmp;}return pre;}
}; 代码真是超简单但是记得我们本来只有prev和current是因为要存断裂开来的current才引入了temp。 并且记得prev最终指向尾节点cur最终指向尾节点后的nullptr所以while的条件是curnullptr。当等于空直接可以返回返回的头节点就是prev。 时间复杂度O(n)空间复杂度O(1) class Solution {
public:ListNode* reverseList(ListNode* head) {return reverse(nullptr,head);}ListNode* reverse(ListNode *pre, ListNode *cur){if(cur nullptr)return pre;else{ListNode *temp cur-next; cur - next pre;return reverse(cur, temp);}}
}; 以上是递归写法是双指针法的变体。 4. 两两交换链表中的节点Leetcode24. 20230901 /*** 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* swapPairs(ListNode* head) {//定义虚拟头节点ListNode *dummynode new ListNode();dummynode - next head;ListNode *cur dummynode;while(cur - next ! nullptr cur - next - next ! nullptr){ListNode *tmp cur - next;ListNode *tmp1 cur - next - next - next;cur - next cur - next - next;cur - next - next tmp;tmp - next tmp1;cur cur - next - next;}return dummynode - next;}
}; 这一题画图非常重要 5. 删除链表的倒数第N个节点删除某节点指针需要跑到节点前面20230902 本题是快慢指针的经典使用 /*** 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* removeNthFromEnd(ListNode* head, int n) { ListNode *dummynode new ListNode(); dummynode-next head;ListNode *fast head;ListNode *slow dummynode;while(n-- fast ! nullptr){fast fast-next;}while(fast ! nullptr){fast fast-next;slow slow-next;}ListNode *tmp slow-next;slow-next slow-next-next;delete tmp;return dummynode-next;}
}; 时间复杂度O(n)空间复杂度O(1) 6. 链表相交 面试题 02.07. 重点在于尾部对齐思想和非值相等20230902 尾部对齐这个没啥好说的跟上题快慢指针一样思想记住就行 非值相等……简单来说就是我做题的时候以为下面这个示例应该1的时候就是相交的其实测试用例应该是真给了两个相交链表导致值相等的时候不一定相交反而是直接判断指针curA! curB相等才对。 /*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {// 尾部对齐int lengthA 0, lengthB 0;ListNode *curA headA, *curB headB;while (headA ! nullptr){headA headA-next;lengthA;}while (headB ! nullptr){headB headB-next;lengthB;}if(lengthA lengthB){int tmp lengthA - lengthB;while(tmp--){curA curA-next;} }else{int tmp lengthB - lengthA;while(tmp--){curB curB-next;} }// 移动指针找交点while(curA ! nullptr curA! curB)//本来写的是curA-val ! curB-val{curA curA-next;curB curB-next;}return curA;}
}; 7. 环形链表II Leetcode142. 20230903 本题主要是数学证明居多。 这一题是这两篇唯一让我觉得有些心虚的因为这个数学证明我自己肯定不会去想出来让我们来看一下本题的思路 /*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode *detectCycle(ListNode *head) {ListNode *fast head;ListNode *slow head;while(fast ! nullptr fast-next !nullptr){fast fast-next -next;slow slow-next;if(fast slow){ListNode *index1 fast;ListNode *index2 head;while(index1 ! index2){index1 index1-next;index2 index2-next;}return index1;}}return nullptr;}
}; 首先是快慢双指针从头开始快指针到空就肯定无环然后快指针两倍速入环慢指针跟着一倍速入慢指针走不到一圈必被快指针追上考虑最坏情形慢指针刚入快指针刚比他快一格当慢指针走完1环快指针肯定走完2环。所以慢在走1环的中途肯定被追上。 我们列出的数学式子是2(xy)xyn(yz)注意这个2就是因为快指针两格两格跨又跟慢指针同时触发所以是走了慢指针两倍距离。然后可以看到x(n-1)(yz)y 那么如果我们要求入环点就是求这个x。考虑被追上的这个情形下正好有了y的尾部那么走x与从y走最终就会在y头部相遇这个从刚刚的式子可以几何理解不论多走几圈最终都是在y头部相遇那么就得到了最后的点。[对于这一段真的是有点心虚自己推不出来笨笨again] 链表到此就结束了说谢谢随想录。 8. 两数相加 leetcode2. 20231025 时隔一个月在leetcode题单上看到这个第二题是之前被我看过、提交过、放弃过的题就在学会链表之后自己尝试了一下调试了很多遍好在最后通过了。但是我并不知道这一题dummynode有什么用也忘记了怎么写并且忘记了如何优雅地循环新增node所以只能抱着“节省空间”的想法基于一个链表去进行求和写出了如下丑陋冗余的代码 /*** 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* addTwoNumbers(ListNode* l1, ListNode* l2) {ListNode *node l2;ListNode *result l2;bool carry 0;while(l1 ! nullptr l2 ! nullptr){int temp l1-val l2-val carry;carry 0;l1 l1-next;l2 l2-next;if(temp 9){carry 1;}node-val temp % 10;if(l2 ! nullptr)node node-next;}if(l1 nullptr l2 nullptr carry 1){ListNode *tailnode new ListNode();tailnode-val 1;node-next tailnode; }while(l1 ! nullptr){node - next l1;node node-next;int temp l1-val carry;carry 0;l1 l1-next;if(temp 9){carry 1;}node-val temp % 10;if(l1 nullptr carry 1){ListNode *tailnode new ListNode();tailnode-val 1;node-next tailnode; }}while(l2 ! nullptr){int temp l2-val carry;carry 0;l2 l2-next;if(temp 9){carry 1;}node-val temp % 10;if(l2 nullptr carry 1){ListNode *tailnode new ListNode();tailnode-val 1;node-next tailnode; }node node-next;}return result; }}; 后来看到了官方题解。 官方题解中使用了 int n1 l1 ? l1-val: 0; 也就是说l1nullptr的时候自动就是0值可以直接用 然后又用了 if (!head) {head tail new ListNode(sum % 10);} else {tail-next new ListNode(sum % 10);tail tail-next;} 意思是说tail往后增长是直接用next去new一个这样的话就可以实现我想实现的循环新增 然后如何让两个链表一起停止呢只要对l1和l2分别判断是不是为空如果为空就不next反之继续next
