1. 力扣刷题实战四道经典C算法题深度解析作为程序员算法能力是基本功。力扣LeetCode作为全球知名的技术刷题平台汇集了大量优质算法题目。今天我想分享四道中等难度但极具代表性的题目24题两两交换链表中的节点、19题删除链表的倒数第N个节点、160题相交链表和142题环形链表II。这四道题涵盖了链表操作中的多个核心考点非常适合用来检验和提升C编程能力。2. 环境准备与基础配置2.1 C开发环境搭建在开始刷题前确保你的开发环境配置正确。我推荐使用VS Code作为编辑器配合MinGW或MSVC编译器。如果你遇到Microsoft Visual C 14.0 or greater is required这类错误需要安装对应的Visual C Redistributable。安装步骤下载并安装Visual Studio Build Tools选择C桌面开发工作负载确保勾选Windows SDK和最新MSVC工具集2.2 力扣刷题模板在力扣上刷题时通常会给你一个函数签名。例如24题的初始代码/** * 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) { // 你的代码 } };3. 题目解析与实现3.1 24题两两交换链表中的节点这道题要求我们交换链表中相邻的两个节点。例如 输入1-2-3-4 输出2-1-4-3解题思路使用虚拟头节点(dummy node)简化边界条件处理维护三个指针prev、curr和next每次交换curr和next节点更新指针位置继续下一轮交换C实现ListNode* swapPairs(ListNode* head) { ListNode dummy(0); dummy.next head; ListNode* prev dummy; while (prev-next prev-next-next) { ListNode* first prev-next; ListNode* second first-next; // 交换节点 first-next second-next; second-next first; prev-next second; // 移动prev指针 prev first; } return dummy.next; }注意事项必须检查prev-next和prev-next-next是否存在交换后要正确更新prev指针位置使用虚拟头节点可以避免处理头节点交换的特殊情况3.2 19题删除链表的倒数第N个节点这道题要求删除链表中倒数第N个节点。例如 输入1-2-3-4-5, n2 输出1-2-3-5解题思路使用快慢指针技巧快指针先走N步然后快慢指针同时前进直到快指针到达末尾此时慢指针指向的就是要删除节点的前驱C实现ListNode* removeNthFromEnd(ListNode* head, int n) { ListNode dummy(0); dummy.next head; ListNode *fast dummy, *slow dummy; // 快指针先走n步 for (int i 0; i n; i) { fast fast-next; } // 同时移动快慢指针 while (fast-next) { fast fast-next; slow slow-next; } // 删除节点 ListNode* toDelete slow-next; slow-next slow-next-next; delete toDelete; // 实际面试中可能不需要这行 return dummy.next; }常见错误没有处理删除头节点的情况使用虚拟头节点可避免n的值大于链表长度题目保证n有效指针移动步数错误3.3 160题相交链表这道题要求找出两个单链表相交的起始节点。例如 链表A4-1-8-4-5 链表B5-6-1-8-4-5 相交于节点8解题思路双指针法指针pA从headA开始pB从headB开始当pA到达末尾时跳转到headB当pB到达末尾时跳转到headA如果两链表相交指针会在交点相遇否则会同时到达nullptrC实现ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { ListNode *pA headA, *pB headB; while (pA ! pB) { pA pA ? pA-next : headB; pB pB ? pB-next : headA; } return pA; }关键点这个解法巧妙地处理了长度不同的情况时间复杂度O(mn)空间复杂度O(1)如果两链表不相交最终pA和pB会同时为nullptr3.4 142题环形链表II这道题要求找出链表中环的起始节点。例如 输入3-2-0--4-4指向2 输出返回节点2解题思路Floyd判圈算法使用快慢指针快指针每次两步慢指针每次一步如果存在环两指针必定会相遇相遇后将一个指针移回head然后两指针每次一步前进再次相遇的节点就是环的起点C实现ListNode *detectCycle(ListNode *head) { ListNode *slow head, *fast head; // 检测是否有环 while (fast fast-next) { slow slow-next; fast fast-next-next; if (slow fast) break; } // 无环情况 if (!fast || !fast-next) return nullptr; // 找环起点 slow head; while (slow ! fast) { slow slow-next; fast fast-next; } return slow; }数学原理 设链表头到环起点距离为a环起点到相遇点距离为b相遇点到环起点距离为c 根据快慢指针关系2(ab) abcb → a c4. 刷题技巧与优化4.1 链表问题通用技巧虚拟头节点几乎可以解决所有头节点特殊处理的问题双指针快慢指针、前后指针等是链表问题的利器画图分析在纸上画出链表结构能帮助理清思路边界检查空链表、单节点链表等特殊情况要单独考虑4.2 C特定优化使用const引用当不需要修改链表时使用const ListNode* 参数内存管理实际工程中要注意释放删除的节点结构化绑定C17后可以使用auto [val, next]来解构节点智能指针在实际项目中考虑使用unique_ptr管理链表内存4.3 调试技巧打印链表编写一个辅助函数打印链表内容void printList(ListNode* head) { while (head) { cout head-val -; head head-next; } cout nullptr endl; }构造测试用例包括普通情况、边界情况和错误情况// 测试两两交换 ListNode* createList(vectorint vals) { ListNode dummy(0); ListNode* curr dummy; for (int val : vals) { curr-next new ListNode(val); curr curr-next; } return dummy.next; }5. 常见问题与解决方案5.1 指针操作错误问题访问空指针或野指针解决每次访问指针前检查是否为nullptr使用调试器观察指针值初始化指针为nullptr5.2 内存泄漏问题删除节点后没有释放内存解决在删除节点前保存next指针使用delete释放内存或者使用智能指针管理5.3 逻辑错误问题循环条件或指针移动错误解决在纸上模拟运行过程添加详细的日志输出使用小规模测试用例验证5.4 性能优化问题算法时间复杂度过高解决分析时间复杂度寻找O(n)或O(1)空间解法避免不必要的遍历利用数学规律简化问题6. 进阶练习建议掌握这四道题后可以尝试以下进阶练习反转链表力扣206题合并两个有序链表力扣21题复制带随机指针的链表力扣138题重排链表力扣143题K个一组翻转链表力扣25题对于链表问题我个人的经验是多画图、多模拟。刚开始刷题时我经常因为指针操作错误导致程序崩溃。后来发现在纸上画出每个步骤的指针变化能大大减少这类错误。另外力扣的讨论区有很多优质解法学习别人的思路也是快速提升的好方法。 C++链表算法实战：力扣四题深度解析与优化技巧
1. 力扣刷题实战四道经典C算法题深度解析作为程序员算法能力是基本功。力扣LeetCode作为全球知名的技术刷题平台汇集了大量优质算法题目。今天我想分享四道中等难度但极具代表性的题目24题两两交换链表中的节点、19题删除链表的倒数第N个节点、160题相交链表和142题环形链表II。这四道题涵盖了链表操作中的多个核心考点非常适合用来检验和提升C编程能力。2. 环境准备与基础配置2.1 C开发环境搭建在开始刷题前确保你的开发环境配置正确。我推荐使用VS Code作为编辑器配合MinGW或MSVC编译器。如果你遇到Microsoft Visual C 14.0 or greater is required这类错误需要安装对应的Visual C Redistributable。安装步骤下载并安装Visual Studio Build Tools选择C桌面开发工作负载确保勾选Windows SDK和最新MSVC工具集2.2 力扣刷题模板在力扣上刷题时通常会给你一个函数签名。例如24题的初始代码/** * 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) { // 你的代码 } };3. 题目解析与实现3.1 24题两两交换链表中的节点这道题要求我们交换链表中相邻的两个节点。例如 输入1-2-3-4 输出2-1-4-3解题思路使用虚拟头节点(dummy node)简化边界条件处理维护三个指针prev、curr和next每次交换curr和next节点更新指针位置继续下一轮交换C实现ListNode* swapPairs(ListNode* head) { ListNode dummy(0); dummy.next head; ListNode* prev dummy; while (prev-next prev-next-next) { ListNode* first prev-next; ListNode* second first-next; // 交换节点 first-next second-next; second-next first; prev-next second; // 移动prev指针 prev first; } return dummy.next; }注意事项必须检查prev-next和prev-next-next是否存在交换后要正确更新prev指针位置使用虚拟头节点可以避免处理头节点交换的特殊情况3.2 19题删除链表的倒数第N个节点这道题要求删除链表中倒数第N个节点。例如 输入1-2-3-4-5, n2 输出1-2-3-5解题思路使用快慢指针技巧快指针先走N步然后快慢指针同时前进直到快指针到达末尾此时慢指针指向的就是要删除节点的前驱C实现ListNode* removeNthFromEnd(ListNode* head, int n) { ListNode dummy(0); dummy.next head; ListNode *fast dummy, *slow dummy; // 快指针先走n步 for (int i 0; i n; i) { fast fast-next; } // 同时移动快慢指针 while (fast-next) { fast fast-next; slow slow-next; } // 删除节点 ListNode* toDelete slow-next; slow-next slow-next-next; delete toDelete; // 实际面试中可能不需要这行 return dummy.next; }常见错误没有处理删除头节点的情况使用虚拟头节点可避免n的值大于链表长度题目保证n有效指针移动步数错误3.3 160题相交链表这道题要求找出两个单链表相交的起始节点。例如 链表A4-1-8-4-5 链表B5-6-1-8-4-5 相交于节点8解题思路双指针法指针pA从headA开始pB从headB开始当pA到达末尾时跳转到headB当pB到达末尾时跳转到headA如果两链表相交指针会在交点相遇否则会同时到达nullptrC实现ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { ListNode *pA headA, *pB headB; while (pA ! pB) { pA pA ? pA-next : headB; pB pB ? pB-next : headA; } return pA; }关键点这个解法巧妙地处理了长度不同的情况时间复杂度O(mn)空间复杂度O(1)如果两链表不相交最终pA和pB会同时为nullptr3.4 142题环形链表II这道题要求找出链表中环的起始节点。例如 输入3-2-0--4-4指向2 输出返回节点2解题思路Floyd判圈算法使用快慢指针快指针每次两步慢指针每次一步如果存在环两指针必定会相遇相遇后将一个指针移回head然后两指针每次一步前进再次相遇的节点就是环的起点C实现ListNode *detectCycle(ListNode *head) { ListNode *slow head, *fast head; // 检测是否有环 while (fast fast-next) { slow slow-next; fast fast-next-next; if (slow fast) break; } // 无环情况 if (!fast || !fast-next) return nullptr; // 找环起点 slow head; while (slow ! fast) { slow slow-next; fast fast-next; } return slow; }数学原理 设链表头到环起点距离为a环起点到相遇点距离为b相遇点到环起点距离为c 根据快慢指针关系2(ab) abcb → a c4. 刷题技巧与优化4.1 链表问题通用技巧虚拟头节点几乎可以解决所有头节点特殊处理的问题双指针快慢指针、前后指针等是链表问题的利器画图分析在纸上画出链表结构能帮助理清思路边界检查空链表、单节点链表等特殊情况要单独考虑4.2 C特定优化使用const引用当不需要修改链表时使用const ListNode* 参数内存管理实际工程中要注意释放删除的节点结构化绑定C17后可以使用auto [val, next]来解构节点智能指针在实际项目中考虑使用unique_ptr管理链表内存4.3 调试技巧打印链表编写一个辅助函数打印链表内容void printList(ListNode* head) { while (head) { cout head-val -; head head-next; } cout nullptr endl; }构造测试用例包括普通情况、边界情况和错误情况// 测试两两交换 ListNode* createList(vectorint vals) { ListNode dummy(0); ListNode* curr dummy; for (int val : vals) { curr-next new ListNode(val); curr curr-next; } return dummy.next; }5. 常见问题与解决方案5.1 指针操作错误问题访问空指针或野指针解决每次访问指针前检查是否为nullptr使用调试器观察指针值初始化指针为nullptr5.2 内存泄漏问题删除节点后没有释放内存解决在删除节点前保存next指针使用delete释放内存或者使用智能指针管理5.3 逻辑错误问题循环条件或指针移动错误解决在纸上模拟运行过程添加详细的日志输出使用小规模测试用例验证5.4 性能优化问题算法时间复杂度过高解决分析时间复杂度寻找O(n)或O(1)空间解法避免不必要的遍历利用数学规律简化问题6. 进阶练习建议掌握这四道题后可以尝试以下进阶练习反转链表力扣206题合并两个有序链表力扣21题复制带随机指针的链表力扣138题重排链表力扣143题K个一组翻转链表力扣25题对于链表问题我个人的经验是多画图、多模拟。刚开始刷题时我经常因为指针操作错误导致程序崩溃。后来发现在纸上画出每个步骤的指针变化能大大减少这类错误。另外力扣的讨论区有很多优质解法学习别人的思路也是快速提升的好方法。