2. 两数相加

转载自Leet Code

题目描述

给定两个非空链表，表示两个非负整数。

每位数字按照逆序存储，每个节点只能存储一位数字。

请你将两个数相加，并且以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例1:

输入：l1 = [2,4,3], l2 = [5,6,4] 输出：[7,0,8]

示例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]

提示:

• 每个链表中的节点数在范围 [1, 100] 内;
• 0 <= Node.val <= 9;
• 题目数据保证列表表示的数字不含前导零;

---

我的代码

$T(N) = O(max(M,N)), S(N) = O(1); $

class MySolution2 {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    	ListNode p1 = l1; ListNode p2 = l2;
    	
    	int add = 0;
    	ListNode ansP = null; ListNode tailP = null;
    	while (p1!=null&&p2!=null)
    	{
    		int sum = p1.val+p2.val+add;
    		int val = sum%10; add = sum/10;
    		ListNode newP = new ListNode(val);
    		
    		if (ansP==null) {
                ansP = newP;tailP = ansP;
            }
    		else {
    			tailP.next = newP; tailP = newP;
    		}
            p1=p1.next; p2=p2.next;
    	}
		ListNode node =  p1!=null?p1:p2;
    	while (node!=null)
    	{
    		int val;
    		if (add==0)
    			val = node.val;
    		else{
        		int sum = node.val+add;
        		val = sum%10; add = sum/10;
    		}

    		ListNode newP = new ListNode(val);
			tailP.next = newP; tailP = newP;
            node = node.next;
    	}
    	if (add!=0) 
        {
    		int val = add;
    		ListNode newP = new ListNode(val);
			tailP.next = newP; tailP = newP;
    	}
    	return ansP;
    }
}