商业网站建设与运营,wordpress插件没有设置,大连网络营销seo,网页设计自学网站两数相加#xff08;medium#xff09;
题目描述
给你两个非空的链表#xff0c;表示两个非负的整数。它们每位数字都是按照逆序的方式存储的#xff0c;并且每个节点只能存储 一位数字。请你将两个数相加#xff0c;并以相同形式返回一个表示和的链表。你可以假设除了数…两数相加medium
题目描述
给你两个非空的链表表示两个非负的整数。它们每位数字都是按照逆序的方式存储的并且每个节点只能存储 一位数字。请你将两个数相加并以相同形式返回一个表示和的链表。你可以假设除了数字 0 之外这两个数都不会以 0 开头。注意点 每个链表中的节点数在范围 [1, 100] 内。0 Node.val 9。题目数据保证列表表示的数字不含前导零。
举例说明
示例 1 输入l1 [2,4,3], l2 [5,6,4]输出[7,0,8]解释342 465 807. 示例 2 输入l1 [0], l2 [0]输出[0] 示例 3 输入l1 [9,9,9,9,9,9,9], l2 [9,9,9,9]输出[8,9,9,9,0,0,0,1]
面试解法
关键词 预先指针短链表补零 思路 对于链表问题返回结果为头结点时通常需要先初始化一个预先指针 pre该指针的下一个节点指向真正的头结点 head。使用预先指针的目的在于链表初始化时无可用节点值而且链表构造过程需要指针移动进而会导致头指针丢失无法返回结果。将两个链表看成是相同长度的进行遍历如果一个链表较短则在前面补 0比如 987 23 987 023 1010每一位计算的同时需要考虑上一位的进位问题而当前位计算结束后同样需要更新进位值如果两个链表全部遍历完毕后进位值为 1则在新链表最前方添加节点 1。 复杂度 时间复杂度O(max(m,n))其中 m 和 n 分别为两个链表的长度因为需要遍历两个链表的全部位置而处理每个位置只需要 O(1) 的时间。空间复杂度O(1)注意返回值不计入空间复杂度。 代码class Solution {public ListNode addTwoNumbers(ListNode l1, ListNode l2) {/** 设立预先指针和遍历指针初始进位值为 0*/ListNode pre new ListNode(0);ListNode cur pre;int carry 0;while (l1 ! null || l2 ! null) {/** 在短链表末尾虚拟添加 0使得两个链表等长*/int value1 l1 null ? 0 : l1.val;int value2 l2 null ? 0 : l2.val;int sum value1 value2 carry;/** 更新进位值并将遍历指针后移*/carry sum / 10;sum % 10;cur.next new ListNode(sum);cur cur.next;/** 将链表指针后移*/if (l1 ! null) {l1 l1.next;}if (l2 ! null) {l2 l2.next;}}/** 处理最后产生进位的问题 */if (carry 1) {cur.next new ListNode(1);}return pre.next;}
}
