欢迎来到李耶的频道【LeetCode面试题】。两数相加题目给你两个非空的链表表示两个非负的整数。它们每位数字都是按照逆序的方式存储的并且每个节点只能存储一位数字。请你将两个数相加并以相同形式返回一个表示和的链表。你可以假设除了数字 0 之外这两个数都不会以 0 开头。输入l1 [2,4,3], l2 [5,6,4] 输出[7,0,8] 解释342 465 807.输入l1 [0], l2 [0] 输出[0]解法一同时遍历模拟加法思路题目给出的链表已经是逆序存储个位在链表头部这正好符合我们从低位到高位做加法的习惯。只需要同时遍历两个链表逐位计算和并维护一个进位变量carry。functionaddTwoNumbers(l1,l2){// 创建一个虚拟头节点方便返回结果链表letdummyHeadnewListNode(0);letcurrdummyHead;letcarry0;// 只要有一个链表没遍历完或者还有进位就继续while(l1!null||l2!null||carry!0){// 取当前节点的值如果节点为空则补0constval1l1?l1.val:0;constval2l2?l2.val:0;constsumval1val2carry;carryMath.floor(sum/10);// 计算进位// 创建新节点值为 sum 的个位数curr.nextnewListNode(sum%10);currcurr.next;// 移动指针if(l1)l1l1.next;if(l2)l2l2.next;}// 返回虚拟头节点的下一个节点即结果链表的头节点returndummyHead.next;}时间复杂度O(max(m, n))其中 m 和 n 分别是两个链表的长度。只需遍历较长的链表一次。空间复杂度O(max(m, n))新链表占用的空间。优势思路最直接完全按照手工加法逻辑实现容易理解和记忆。解法二递归思路递归也能实现同样的效果。递归函数接收两个链表节点和一个进位值返回当前位计算后的新节点并调用自身处理下一位。functionaddTwoNumbers(l1,l2,carry0){// 递归终止条件两个链表都为空且没有进位if(l1nulll2nullcarry0){returnnull;}constval1l1?l1.val:0;constval2l2?l2.val:0;constsumval1val2carry;constnextCarryMath.floor(sum/10);// 创建当前节点并递归构建后续节点constnodenewListNode(sum%10);node.nextaddTwoNumbers(l1?l1.next:null,l2?l2.next:null,nextCarry);returnnode;}时间复杂度O(max(m, n))空间复杂度O(max(m, n))递归调用栈的深度取决于链表的长度。优势代码更简洁、优雅体现了函数式编程思想。扩展题两数相加 II给定两个非空链表链表头部是高位尾部是个位。将两个数相加返回和链表。二进制链表转整数给你一个单链表的引用节点head。链表中每个节点的值不是 0 就是 1。已知此链表是一个整数数字的二进制表示形式返回该链表所表示数字的十进制值。K 个一组翻转链表给你链表的头节点head每k个节点一组进行翻转返回修改后的链表。