力扣hot 100 两数相加
给你两个 非空 的链表,表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的,并且每个节点只能存储 一位 数字。
请你将两个数相加,并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外,这两个数都不会以 0 开头。
实例
输入:l1 = [2,4,3], l2 = [5,6,4]
输出:[7,0,8]
解释:342 + 465 = 807.
基本思路
这道题主要考察 链表双指针技巧 和加法运算过程中对进位的处理。
分析条件
从实例可以看出来 我们需要处理 满 10 进1 的进位问题
用双指针将两条链表的节点相加结果加入到 结果链表里
记录进位情况
public ListNode addTwoNumbers(ListNode l1, ListNode l2) { // 在两条链表上的指针 ListNode p1 = l1, p2 = l2; // 虚拟头结点(构建新链表时的常用技巧) ListNode dummy = new ListNode(-1); // 指针 p 负责构建新链表 ListNode p = dummy; // 记录进位 int carry = 0; // 开始执行加法,两条链表走完且没有进位时才能结束循环 while (p1 != null || p2 != null || carry > 0) { // 先加上 上次的进位 int val = carry; if (p1 != null) { val += p1.val; p1 = p1.next; } if (p2 != null) { val += p2.val; p2 = p2.next; } // 处理进位情况 carry = val / 10; val = val % 10; // 构建新节点 p.next = new ListNode(val); p = p.next; } // 返回结果链表的头结点(去除虚拟头结点) return dummy.next; }
如果截图思路对你有帮助的话,记得给小冷一个赞哦!!!
提交结果
文章知识点与官方知识档案匹配,可进一步学习相关知识
算法技能树leetcode-排序算法493-翻转对4041 人正在系统学习中