定制v,合肥seo搜索优化,做土地租赁买卖的网站有哪些,网站内容协议【问题描述】445. 两数相加 II
给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。你可以假设除了数字 0 之外#xff0c;这两个数字都不会以零开头。进阶#xff1a;如果输入链表不能修改…【问题描述】445. 两数相加 II
给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。你可以假设除了数字 0 之外这两个数字都不会以零开头。进阶如果输入链表不能修改该如何处理换句话说你不能对列表中的节点进行翻转。示例输入(7 - 2 - 4 - 3) (5 - 6 - 4)
输出7 - 8 - 0 - 7来源力扣LeetCode
链接https://leetcode-cn.com/problems/add-two-numbers-ii
著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。【解答思路】
1. 常规思路 链表反转 然后按位相加 (入门)
时间复杂度O(N) 空间复杂度O(1)
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val x; }* }*/
class Solution {public ListNode addTwoNumbers(ListNode l1, ListNode l2) {//反转链表ListNode newl1 reverse(l1);ListNode newl2 reverse(l2);//处理进位 累加的和是否有超过10进位的情况int carry 0;ListNode l3 null;while(newl1! null || newl2 ! null|| carry!0){int n10 , n2 0;//反转后的链表取值并求和if(newl1 null){n1 0;}else{n1 newl1.val;newl1 newl1.next; }if(newl2 null){n2 0;}else{n2 newl2.val;newl2 newl2.next; }int sum n1 n2 carry;//头插法 根据和求当前位置的值 和 进位的值 并连接上链表 ListNode tmp new ListNode(sum%10);tmp.next l3;l3 tmp;carry sum /10;}return l3;}/*将给定头结点的链表反转*/private ListNode reverse(ListNode head){ListNode pre null;while(head!null){ListNode next head.next;head.next pre;pre head;head next;}return pre;}
}
2. 逆序- 栈思想 进阶
时间复杂度O(N) 空间复杂度O(N)
class Solution {public ListNode addTwoNumbers(ListNode l1, ListNode l2) {/*//java stack源码 推荐栈相关的用ArrayDeque类来实现 遵循官方建议所以用ArrayDequeDequeInteger stack1 new ArrayDequeInteger();DequeInteger stack2 new ArrayDequeInteger();*/StackInteger stack1 new Stack();StackInteger stack2 new Stack();//将两个链表分别入栈while(l1!null){stack1.push(l1.val);l1l1.next;}while(l2!null){stack2.push(l2.val);l2 l2.next;}int carry 0;ListNode after null;while(!stack1.isEmpty()||!stack2.isEmpty()||carry!0){//栈先进后出的性质 所以取出的是最后入栈的元素 并求和int n1 stack1.isEmpty()?0:stack1.pop();int n2 stack2.isEmpty()?0:stack2.pop();int sum n1n2carry;//根据和求当前位置的值 和 进位的值 并连接上链表ListNode tmp new ListNode(sum%10);tmp.next after;after tmp;carrysum/10;}return after;}
}【总结】
1.反转链表 头插法多画图理解 /*将给定头结点的链表反转*/private ListNode reverse(ListNode head){ListNode pre null;while(head!null){ListNode next head.next;head.next pre;pre head;head next;}2. 逆序- 栈思想
3. 三目运算符逻辑极度清晰的时候使用
表达式1 ? 表达式2 : 表达式3; ?运算符的含义是先求表达式1的值如果为真则执行表达式2并返回表达式2的结果如果表达式1的值为假则执行表达式3并返回表达式3的结果。
