如何给网站写文章,长沙互联网公司在哪个区,网站建设服务器要求,贵州网络推广介绍文章目录 题目思路Java 链表第 1 步#xff1a;第 2 步#xff1a; 复杂度Code 题目
Problem: 2. 两数相加给你两个 非空 的链表#xff0c;表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的#xff0c;并且每个节点只能存储 一位 数字。请你将两个数相加 链表第 1 步第 2 步 复杂度Code 题目
Problem: 2. 两数相加给你两个 非空 的链表表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的并且每个节点只能存储 一位 数字。请你将两个数相加并以相同形式返回一个表示和的链表。你可以假设除了数字 0 之外这两个数都不会以 0 开头。每个链表中的节点数在范围 [1, 100] 内0 Node.val 9题目数据保证列表表示的数字不含前导零
思路
Java 链表
第 1 步
首先判空然后从头开始低位到高位将 l2 加到 l1 上最后注意 l1 与 l2 长度不同与进位
第 2 步
如果 l2 更长则将更长的直接加入 l1 后如果最后还有进位则需要新创建 ListNode 放在后面注意由于直接判断 l1 null此时会丢失 l1 前一个位置的信息因此需要维护一个 prevL1.next l1通用技巧
复杂度
时间复杂度: 时间复杂度 O ( n ) O(n) O(n) 空间复杂度: 空间复杂度 O ( 1 ) O(1) O(1) Code
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val val; }* ListNode(int val, ListNode next) { this.val val; this.next next; }* }*/
class Solution {/*** Java 链表** 第 1 步* 首先判空* 然后从头开始低位到高位将 l2 加到 l1 上* 最后注意 l1 与 l2 长度不同与进位** 第 2 步* 如果 l2 更长则将更长的直接加入 l1 后* 如果最后还有进位则需要新创建 ListNode 放在后面* 注意由于直接判断 l1 null此时会丢失 l1 前一个位置的信息因此需要维护一个 prevL1.next l1通用技巧**/public ListNode addTwoNumbers(ListNode l1, ListNode l2) {// 判空if (l1 null) {return l2;} else if (l2 null) {return l1;}// 从头开始将 l2 加到 l1 上如果 l2 更长则将更长的直接加入 l1 后注意进位ListNode res l1;int carry 0;ListNode prevL1 new ListNode(0, l1);// 如果最后需要进位则 carry 非 0while (l1 ! null || l2 ! null || carry ! 0) {if (l1 ! null l2 ! null) {l1.val l2.val carry;carry l1.val / 10;l1.val % 10;prevL1 l1;l1 l1.next;l2 l2.next;} else if (l1 ! null) {l1.val carry;carry l1.val / 10;l1.val % 10;prevL1 l1;l1 l1.next;} else if (l2 ! null) {l1 l2;prevL1.next l2;l2 null;} else {prevL1.next new ListNode(carry % 10);carry / 10;}}return res;}
}
