你好我是fengxin_rou这是我的个人主页fengxin_rou的主页❄️欢迎查看我的专栏我的专栏《Java后端学习》、《JAVASE基础》、《JUC并发》、《redis》、《JVM虚拟机》、《MYSQL》、《黑马点评》、《rabbitmq》、《JavaWebAI的talis学习系统》、《苍穹外卖》目录引言第一部分合并两个有序链表LeetCode 211.1 题目描述1.2 解法一迭代法虚拟头节点1.2.1 核心思想1.2.2 算法流程图1.2.3 代码实现1.2.4 逐步解析1.3 解法二递归法1.3.1 核心思想1.3.2 递归调用栈示意图1.3.3 代码实现1.4 复杂度分析1.5 常见错误与优化第二部分两数相加LeetCode 22.1 题目描述2.2 解法递归法与进位处理2.2.1 核心思想2.2.2 递归与进位示意图2.2.3 代码实现2.3 逐步解析2.4 复杂度分析2.5 扩展思考2.5.1 如果链表不是逆序存储怎么办2.5.2 如何处理超大数字第三部分对比与总结3.1 两种链表操作的异同3.2 链表操作通用技巧3.3 复杂度对比最佳实践链表操作通用技巧4.1 链表操作检查清单4.2 性能优化建议常见问题解答FAQQ1为什么选择虚拟头节点Q2递归法什么时候会栈溢出Q3如何判断链表是否有环Q4两数相加问题中如果数字不是逆序存储怎么办Q5如何处理链表中的重复节点参考文献本文深入解析LeetCode两道经典链表算法题提供迭代与递归两种解法配合详细图解和代码分析帮助读者掌握链表操作的核心思想。引言链表作为数据结构的基础在算法面试中占据重要地位。LeetCode上的合并两个有序链表第21题和两数相加第2题是链表操作的经典代表。本文将从问题定义、算法思路、代码实现到复杂度分析进行全面解析帮助读者建立系统的链表解题思维。第一部分合并两个有序链表LeetCode 211.1 题目描述将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。示例1输入l1 [1,2,4], l2 [1,3,4] 输出[1,1,2,3,4,4]1.2 解法一迭代法虚拟头节点1.2.1 核心思想创建虚拟头节点简化边界处理双指针遍历同时遍历两个链表比较节点值构建新链表将较小的节点连接到结果链表处理剩余节点将非空链表的剩余部分直接连接1.2.2 算法流程图1.2.3 代码实现class Solution { public ListNode mergeTwoLists(ListNode list1, ListNode list2) { // 创建虚拟头节点 ListNode dum new ListNode(0), cur dum; // 双指针遍历两个链表 while(list1 ! null list2 ! null){ // 比较节点值选择较小的节点 if(list1.val list2.val){ cur.next list1; list1 list1.next; } else { cur.next list2; list2 list2.next; } cur cur.next; } // 合并尾部连接剩余节点 cur.next list1 ! null ? list1 : list2; // 返回真实头节点 return dum.next; } }1.2.4 逐步解析虚拟头节点ListNode dum new ListNode(0)创建一个值为0的临时节点避免处理头节点的特殊情况while循环确保两个链表都不为空时才继续比较条件判断list1.val list2.val决定选择哪个节点指针移动cur cur.next将结果链表指针后移尾部处理三元运算符选择非空链表连接1.3 解法二递归法1.3.1 核心思想递归终止条件当一个链表为空时返回另一个链表递归关系比较两个链表头节点选择较小的节点递归处理剩余部分构建结果将选择的节点与递归结果连接1.3.2 递归调用栈示意图1.3.3 代码实现class Solution { public ListNode mergeTwoLists(ListNode list1, ListNode list2) { // 递归终止条件 if(list1 null) return list2; if(list2 null) return list1; // 选择较小的节点递归处理剩余部分 if(list1.val list2.val){ list1.next mergeTwoLists(list1.next, list2); return list1; } else { list2.next mergeTwoLists(list1, list2.next); return list2; } } }1.4 复杂度分析解法时间复杂度空间复杂度说明迭代法O(mn)O(1)只使用常数额外空间递归法O(mn)O(mn)递归调用栈的最大深度1.5 常见错误与优化忘记处理空链表确保代码能处理任一链表为空的情况指针移动错误注意cur cur.next必须在节点连接后执行递归深度问题对于超长链表递归可能导致栈溢出内存泄漏Java有垃圾回收但C需要手动管理内存第二部分两数相加LeetCode 22.1 题目描述给你两个非空的链表表示两个非负的整数。它们每位数字都是按照逆序的方式存储的并且每个节点只能存储一位数字。请你将两个数相加并以相同形式返回一个表示和的链表。示例1输入l1 [2,4,3], l2 [5,6,4] 输出[7,0,8] 解释342 465 8072.2 解法递归法与进位处理2.2.1 核心思想递归处理同时遍历两个链表进位记录使用单独变量记录进位值逐位相加计算当前位的和处理进位递归构建创建新节点递归处理下一位2.2.2 递归与进位示意图2.2.3 代码实现class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { return addTwo(l1, l2, 0); } public ListNode addTwo(ListNode l1, ListNode l2, int carry) { // 递归终止条件两个链表都为空且进位为0 if(l1 null l2 null carry 0) { return null; } // 计算当前位的和 int sum carry; // 如果l1不为空加上l1的值 if(l1 ! null) { sum l1.val; l1 l1.next; } // 如果l2不为空加上l2的值 if(l2 ! null) { sum l2.val; l2 l2.next; } // 创建新节点val为当前位数字next为递归结果 // sum % 10 得到当前位sum / 10 得到进位 return new ListNode(sum % 10, addTwo(l1, l2, sum / 10)); } }2.3 逐步解析递归终止当两个链表都为空且进位为0时返回null进位处理carry参数记录上一位的进位值逐位相加依次加上两个链表的当前值新节点构建sum % 10得到当前位数字sum / 10得到进位递归调用将进位传递给下一位的计算2.4 复杂度分析复杂度值说明时间复杂度O(max(m,n))遍历较长的链表空间复杂度O(max(m,n))递归调用栈深度2.5 扩展思考2.5.1 如果链表不是逆序存储怎么办解决方案先反转链表再进行加法运算最后反转结果链表。// 反转链表 private ListNode reverseList(ListNode head) { ListNode prev null, curr head; while(curr ! null) { ListNode next curr.next; curr.next prev; prev curr; curr next; } return prev; }2.5.2 如何处理超大数字解决方案使用字符串模拟加法运算避免数值溢出。第三部分对比与总结3.1 两种链表操作的异同对比维度递归法迭代法核心原理函数自调用依靠递归调用栈保存每一步状态循环遍历依靠指针、变量记录状态进位传递通过函数入参carry传递进位用局部变量carry全程记录进位终止条件两链表为空且进位为 0两链表遍历完毕且进位为 0空间复杂度O(max(m,n))调用栈占用额外空间O(1)仅使用常数级临时变量代码风格代码简洁行数少逻辑抽象步骤清晰直观代码偏冗长优缺点写法优雅链表过长易发生栈溢出运行稳定无栈溢出风险可读性一般适用场景短链表、追求代码简洁长链表、工业级正式开发3.2 链表操作通用技巧虚拟头节点简化边界条件处理双指针技术高效遍历链表递归思维将复杂问题分解为子问题进位处理注意数值溢出和进位传递指针操作确保正确连接节点避免断链3.3 复杂度对比问题迭代法递归法推荐解法合并有序链表O(1)空间O(n)空间迭代法更优两数相加可实现O(n)空间递归法更直观最佳实践链表操作通用技巧4.1 链表操作检查清单空链表处理确保代码能处理空链表或单节点链表头节点特殊性考虑是否需要虚拟头节点指针移动顺序先保存next指针再修改当前指针内存管理C需要手动释放内存Java有垃圾回收边界测试测试空链表、单节点、长链表等边界情况4.2 性能优化建议迭代优于递归对于长链表迭代法更稳定原地操作尽量在原链表上操作减少内存分配尾递归优化某些语言支持尾递归优化批量处理对于频繁操作考虑批量处理提高效率常见问题解答FAQQ1为什么选择虚拟头节点A虚拟头节点可以避免处理头节点的特殊情况使代码更简洁。例如在合并有序链表中不需要判断结果链表是否为空。Q2递归法什么时候会栈溢出A当链表长度超过调用栈深度限制时通常几千到几万节点递归会导致栈溢出。此时应使用迭代法。Q3如何判断链表是否有环A使用快慢指针法Floyd判圈算法。快指针每次走两步慢指针每次走一步如果相遇则有环。Q4两数相加问题中如果数字不是逆序存储怎么办A可以先反转链表再进行加法运算最后反转结果链表。或者使用栈来模拟逆序处理。Q5如何处理链表中的重复节点A可以使用哈希表记录已出现的节点值或者在排序后进行去重操作。参考文献LeetCode 21. 合并两个有序链表LeetCode 2. 两数相加