Leetcode 02
Published:
两数相加
两数相加 [medium]
给出两个非空的链表用来表示两个非负的整数。其中，它们各自的位数是按照逆序的方式存储的，并且它们的每个节点只能存储 一位数字。
将这两个数相加，返回一个新的链表来表示它们的和。
Example
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807
思路
注意：直接把两个数字相加的老实人们，数字太大会溢出的
计算每一位相加的结果，carry表示进不进位 -> 0或1
时间复杂度：时间复杂度：O(max(m, n))，m和n分别表示l1和l2的长度
空间复杂度：O(max(m, n))， 新列表的长度最多为max(m,n)+1
Solution
/**
* 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 dummyHead = new ListNode(0);
ListNode p1 = l1, p2 = l2, curr = dummyHead;
int carry = 0;
while (p1 != null || p2 != null){
int n1 = p1 != null ? p1.val:0;
int n2 = p2 != null ? p2.val:0;
int sum = n1 + n2 + carry;
curr.next = new ListNode(sum %10);
carry = sum/10;
curr = curr.next;
if (p1!=null) p1 = p1.next;
if (p2!=null) p2 = p2.next;
}
if (carry >0){
curr.next = new ListNode(1);
}
return dummyHead.next;
}
}