[特殊字符] LeetCode 92. 反转链表 II（C语言详解｜一趟扫描｜头插法）

题目描述给你单链表的头指针head和两个整数left和rightleft right请你反转从位置left到位置right的链表节点并返回反转后的链表。示例输入head [1,2,3,4,5], left 2, right 4 输出[1,4,3,2,5]输入head [5], left 1, right 1 输出[5] 解题思路这道题的关键在于只反转链表的某一段而不是整个链表如果你用“先截断再反转再拼接”的方式会比较繁琐。更优解头插法一次遍历原地完成 核心思想重点1️⃣ 引入虚拟头节点dummy作用避免left 1时特殊处理dummy - 1 - 2 - 3 - 4 - 52️⃣ 找到反转起点前一个节点prepre 停在 left 的前一个位置3️⃣ 使用头插法进行局部反转每次把cur-next插到pre后面 图解过程重点理解初始状态dummy - 1 - 2 - 3 - 4 - 5 ↑ pre ↑ cur第一次操作把3插到1后面dummy - 1 - 3 - 2 - 4 - 5第二次操作把4插到1后面dummy - 1 - 4 - 3 - 2 - 5 C语言代码实现/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* reverseBetween(struct ListNode* head, int left, int right) { if (!head || left right) return head; // 虚拟头节点 struct ListNode dummy; dummy.next head; struct ListNode* pre dummy; // 1. 找到 left 前一个节点 for (int i 1; i left; i) { pre pre-next; } // 2. 当前节点 struct ListNode* cur pre-next; // 3. 头插法反转 for (int i 0; i right - left; i) { struct ListNode* next cur-next; cur-next next-next; next-next pre-next; pre-next next; } return dummy.next; }⏱️ 复杂度分析类型复杂度时间复杂度O(n)空间复杂度O(1)⚠️ 易错点总结❌ 1. 没有使用 dummy 节点 会导致left 1时出错❌ 2. 循环次数写错for (i right - left)不是❌ 3. 指针操作顺序错误必须严格按照cur-next next-next; next-next pre-next; pre-next next; 拓展这道题是以下题目的基础反转链表整体反转K 个一组翻转链表两两交换链表节点掌握“头插法” 链表题通关钥匙 总结一句话总结在区间 [left, right] 内通过头插法不断把后面的节点插到前面实现局部反转