企业官网建设流程全解析

qq登录网站怎么做,在线直播网站建设,今天邯郸下的紧急通知,互联网公司排名2021前100强1 题目 92. 反转链表 II 给你单链表的头指针 head 和两个整数 left 和 right #xff0c;其中 left right 。请你反转从位置 left 到位置 right 的链表节点#xff0c;返回 反转后的链表 。 示例 1#xff1a; 输入#xff1a;head [1,2,3,4,5], left 2, right …1 题目92. 反转链表 II给你单链表的头指针head和两个整数left和right其中left right。请你反转从位置left到位置right的链表节点返回反转后的链表。示例 1输入head [1,2,3,4,5], left 2, right 4输出[1,4,3,2,5]示例 2输入head [5], left 1, right 1输出[5]提示链表中节点数目为n1 n 500-500 Node.val 5001 left right n进阶你可以使用一趟扫描完成反转吗2 代码实现/** * 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* reverseBetween(ListNode* head, int left, int right) { ListNode* dummy new ListNode(0) ; dummy - next head ; ListNode* pre dummy; for (int i 0 ; i left -1 ;i){ pre pre - next ; } ListNode* cur pre - next ; ListNode* tail cur ; ListNode* prev nullptr; for (int j left ; j right 1; j){ ListNode* temp cur - next ; cur - next prev ; prev cur ; cur temp ; } pre - next prev; tail - next cur ; ListNode* newHead dummy - next ; delete dummy; return newHead; } };思考这道题目是部分链表进行了反转操作我想大概的思路是把链表分成三段1.从 head 到 left 这一段要保存好不变 2.从 left 到 right 。 这一段进行翻转的操作 3.从 right 到 最后一个节点 这一段保存好 不变 但是分成三段怎么防止最后一段第三部分的节点不丢失呢难道遍历两趟 第一次划分 第二次实现翻转-----不太清晰看下ai怎么写cpp实现这个leetcode模式核心代码。解题思路要在一趟扫描中完成反转核心思路是定位边界先找到left位置的前一个节点记为pre以及left位置的节点记为cur这是反转段的起点。局部反转从cur开始依次将cur的下一个节点 “插入” 到pre的后面循环执行right-left次完成left到right段的反转。衔接链表整个过程中无需拆分链表再拼接通过调整指针指向直接完成局部反转避免丢失后续节点。C 代码实现LeetCode 核心代码模式// 定义链表节点结构LeetCode 环境已内置此处仅为示意 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* reverseBetween(ListNode* head, int left, int right) { // 虚拟头节点避免处理left1时的边界问题头节点无前驱 ListNode* dummy new ListNode(0); dummy-next head; // 1. 找到left位置的前一个节点pre ListNode* pre dummy; for (int i 1; i left; i) { pre pre-next; } // cur是反转段的第一个节点left位置 ListNode* cur pre-next; // 循环right-left次完成局部反转 for (int i 0; i right - left; i) { // next_node是cur的下一个节点待反转的节点 ListNode* next_node cur-next; // 步骤1cur跳过next_node指向next_node的下一个节点 cur-next next_node-next; // 步骤2next_node插入到pre的后面成为反转段的新头部 next_node-next pre-next; // 步骤3pre指向新的反转段头部next_node pre-next next_node; } // 虚拟头节点的下一个节点是新链表的头 ListNode* new_head dummy-next; delete dummy; // 释放虚拟节点避免内存泄漏 return new_head; } };代码关键部分解释虚拟头节点dummy作用统一处理 “left1”头节点无前驱的边界情况无需单独判断简化逻辑。注意使用后要释放内存避免内存泄漏。定位前驱节点pre循环left-1次让pre指向left位置的前一个节点例如示例 1 中left2pre最终指向节点 1。局部反转核心循环以示例 1 为例left2, right4循环 2 次初始状态pre1, cur2待反转节点是 3、4。第一次循环处理节点 3next_node3cur-next4节点 2 指向 4next_node-next2节点 3 指向 2pre-next3节点 1 指向 3→ 链表变为1-3-2-4-5。第二次循环处理节点 4next_node4cur-next5节点 2 指向 5next_node-next3节点 4 指向 3pre-next4节点 1 指向 4→ 链表变为1-4-3-2-5完成反转。时间复杂度O (n)仅一趟扫描n 为链表长度满足进阶要求空间复杂度O (1)仅使用常数个临时节点。自己写的代码乱七八糟/** * 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* reverseBetween(ListNode* head, int left, int right) { ListNode* dummy new ListNode(0); dummy - next head ; ListNode* cur head ; for (int i 0 ; i left ; i){ cur cur - next ; } ListNode* prev cur ; for (int j left ; j right ; j){ ListNode* temp cur - next ; cur - next prev ; prev cur ; cur temp ; } head dummy - next ; delete dummy ; return head ; } };代码问题逐条拆解1. 反转起点定位错误最核心// 错误代码 for (int i 0 ; i left ; i){ cur cur - next ; }假设left2初始curhead(1)循环执行 2 次后cur会指向 3而非预期的 2相当于定位到了left1的位置完全偏离了反转起点。更严重的是你没有保存left位置的前驱节点比如示例 1 中节点 1反转后无法把前半段链表和反转后的区间衔接起来。2. 反转逻辑错误导致链表断裂// 错误代码 ListNode* prev cur ; for (int j left ; j right ; j){ ListNode* temp cur - next ; cur - next prev ; // 这里会让当前节点指向自己的前驱形成环 prev cur ; cur temp ; }初始prevcur比如 cur3第一次循环时cur-nextprev会让 3 的 next 指向 3自己直接形成环后续节点全部丢失。常规链表反转的prev初始值应该是nullptr且需要控制反转的节点数量为right-left1而非right-left。3. 无链表衔接步骤反转结果无效你的代码全程没有调整dummy或原链表的指针指向反转后的节点无法 “接回” 原链表最终返回的还是原始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* reverseBetween(ListNode* head, int left, int right) { ListNode* dummy new ListNode(0) ; dummy - next head ; ListNode* pre dummy; for (int i 0 ; i left -1 ;i){ pre pre - next ; } ListNode* cur pre - next ; ListNode* tail cur ; ListNode* prev nullptr; for (int j left ; j right 1; j){ ListNode* temp cur - next ; cur - next prev ; prev cur ; cur temp ; } pre - next prev; tail - next cur ; ListNode* newHead dummy - next ; delete dummy; return newHead; } };疑惑从dummy开始走的话不是left就好吗为什么要减去1ListNode* pre dummy; for (int i 0 ; i left -1 ;i){ pre pre - next ; }先明确核心目标pre的作用是定位到left位置节点的前驱节点比如left2时pre要指向节点 1这样后续才能把反转后的区间 “接” 在pre后面。要找的是前驱节点为什么是left-1次用例子拆解假设left2对应链表节点是第二个节点值为 2我们一步步看循环次数的逻辑循环次数pre的初始位置循环条件i left-1即i 1循环后pre的位置说明初始状态dummy指向节点 1 的前一个-dummydummy是第 0 个 “虚拟节点”节点 1 是第 1 个节点 2 是第 2 个i0dummy0 1→ 执行pre dummy-next→ 节点 1这是left-11次循环的唯一一次执行i1节点 11 1→ 不执行节点 1循环结束pre正好是节点 2left2的前驱如果按你的想法写成i left即i 2会发生什么i0pre从dummy→节点 1i1pre从节点 1→节点 2循环结束后pre指向节点 2left 位置本身而非前驱节点后续无法衔接反转区间。再用通用规律总结我们给链表节点做 “位置编号”从 1 开始dummy虚拟节点编号 0是节点 1 的前驱节点 1编号 1是节点 2 的前驱节点 2编号 2是节点 3 的前驱...节点k编号k是节点k1的前驱要找到节点left的前驱就是找编号为left-1的节点从编号 0 的dummy出发需要走left-1步循环left-1次才能到达编号left-1的节点。极端情况验证left1如果left1要反转第一个节点left-10循环条件i 0不执行pre停在dummy这正是我们需要的因为第一个节点的前驱就是dummy完美适配边界场景。总结pre的目标是left 位置节点的前驱而非 left 位置本身从dummy编号 0出发到编号left-1的前驱节点需要走left-1步循环left-1次如果写成i left会多走 1 步导致pre指向 left 位置本身失去 “前驱” 的作用后续无法衔接反转区间。简单记找前驱走left-1步找自身走left步。这里我们要找前驱所以是left-1次循环。3 小结链表的部分写的好艰辛我感受到一个很重要的特点就是指针有自己的职能不能混用。有点像化学里的试管——不能把试剂随意乱放在同一根试管里面。为什么这样说呢首先虚拟头节点的dummy通常是头节点有修改的情况下使用防止丢失节点然后cur就只是遍历 pre tail 存放好部分反转链表的头和尾在反转过程中temp 就作为一个容器防止成环、节点丢失 、逻辑混乱...各有职能 各司其职 。 而我一开始混乱的代码总是觉得这个节点也许可以复用但考虑不好就会有很多问题。第二个就是经常容易出错的循环条件这个最好还是在写代码前考虑好边界用模拟数据走一遍。刷leetcode不仅仅是码字会语法是最小的一部分草稿纸上得出来的思路用程序实现更重要。链表这一块还没上道多练练找找感觉。------------------------召唤ai助教~你在学习反转链表 II 这个题目时不仅自己动手尝试了代码还深入思考了指针的职能和循环边界问题这种复盘和总结的方式特别棒我先帮你把核心疑问彻底讲透再巩固你总结的关键点让你对链表局部反转的逻辑理解更扎实。一、先彻底解答你的核心疑惑为什么循环次数是left - 1你已经意识到pre的目标是找到left 位置节点的前驱节点我们用更直观的方式拆解这个循环逻辑1. 先明确 “位置编号” 和 “步数” 的对应关系我们给链表节点做 “位置标记”结合 dummy 虚拟头dummy 节点位置 0是真正头节点的前驱原链表第 1 个节点head位置 1原链表第 2 个节点位置 2...原链表第 left 个节点位置 left2. 目标从 dummy位置 0走到 left 节点的前驱位置 left-1要从位置 0 到位置left-1需要走left-1步对应循环次数就是left-1次。3. 用具体例子验证left2循环变量 i循环条件i left-1即i 1pre 位置变化初始-dummy0i0成立执行循环pre → 位置 1节点 1i1不成立循环结束停在位置 1最终 pre 正好是 left2 节点节点 2的前驱这就是循环次数必须是left-1的核心原因。如果写成i lefti2会多走一步i1 时循环仍成立pre 会走到位置 2节点 2也就是 left 节点本身失去了 “前驱” 的作用后续无法衔接反转后的链表。二、你总结的 “指针职能” 思路我帮你提炼得更清晰你说 “指针有自己的职能不能混用”这个感悟特别精准我们把这段代码里的每个指针 “职能” 明确下来指针名核心职能dummy统一处理边界比如 left1 时原头节点没有前驱避免单独判断头节点场景pre固定指向 “反转区间的前驱节点”是衔接前半段和反转段的 “锚点”cur遍历反转区间的节点是反转操作的 “当前节点”tail记录反转区间的原始第一个节点反转后会变成反转段的最后一个节点用于衔接后半段prev反转链表时的 “前驱节点”常规链表反转的经典指针最终指向反转段的新头节点temp临时保存 cur 的下一个节点防止反转时丢失后续节点避免链表断裂你的第一版代码出错核心就是指针职能混乱比如让 cur 既负责定位又负责反转且没有 pre/tail 这类 “锚点指针”导致反转后链表衔接不上。三、循环条件的 “避坑技巧”你提到 “循环条件要先用模拟数据走一遍”这是链表题的关键技巧我补充两个实用方法小例子验证写循环前用最简单的例子比如 left2、right4手动走一遍循环次数确认边界比如 j 从 left 到 right1共right-left1次循环正好反转 right-left1 个节点。明确循环目标先想 “这个循环要做什么”再推导次数找前驱循环left-1次 → 到 left 节点的前驱反转区间循环right-left1次 → 反转 left 到 right 的所有节点插入式反转进阶写法循环right-left次 → 逐个把节点插入到前驱后总结pre循环次数是left-1的核心目标是找到 left 节点的前驱从 dummy位置 0到前驱位置 left-1需要走left-1步。链表局部反转的关键用pre前锚点和tail后锚点固定反转区间的前后边界避免链表断裂每个指针各司其职不混用。链表题避坑核心先在草稿纸上明确指针职能和循环目标用小例子验证循环边界再动手写代码。你现在已经能复盘自己的错误还能总结出 “指针职能” 这种核心规律说明已经在理解链表的本质了 —— 链表题的关键从来不是语法而是指针的定位和衔接逻辑多练几个局部反转、删除、插入的题目很快就能找到感觉