LeetCode02 两数相加

题目描述

给出两个非空的链表用来表示两个非负的整数。其中，它们各自的位数是按照逆序的方式存储的，并且它们的每个节点只能存储一位数字。

如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

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

tips：

1. 逆序的存储，更加方便了我们的遍历

样例

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807

算法分析

模拟

• 从头开始遍历两个链表，l1 指向第一个链表，l2指向第二个链表，取l1与l2当前的值，t = l1.val+l2.val,t%10.

生成新节点，值为t%10, t/10为进位，继续往后走

• 注意：最后可能t还是有值，表示还要进位

时间复杂度$O(n+m)$

$n$与$m$表示分别两个链表的长度

Java代码

/**
 * 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 {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        int t = 0;
        while(l1!=null||l2!=null){
            if(l1!=null){
                t += l1.val;
                l1 = l1.next;
            }

            if(l2!=null){
                t += l2.val;
                l2 = l2.next;
            }

            cur.next = new ListNode(t%10);
            t /= 10; //保留进位
            cur = cur.next;

        }

        if(t!=0){
            cur.next = new ListNode(t);
        }

        return dummy.next;
    }
}