445. 两数相加 II

淡淡笔墨，浅浅细语，挥不尽滴点离人泪，诉不完几许苦寒愁，月淡银河，落叶纷纷雨，
饮一杯浊酒，断尽愁人肠，谁为谁痴谁轻狂，此情此景此时休。

LC每日一题，参考445. 两数相加 II。

题目

给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。

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

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

解题思路

• 反转链表：直接反转两个链表后相加处理进位,结果再反转。
• 栈：先用栈保存链表值,再相加处理,反向构建链表。

反转链表

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        //考虑反转链表后 按位相加记录进位
        l1 = get(l1);
        l2 = get(l2);
        ListNode dummy = new ListNode(),ans = dummy;
        int jin = 0;
        while(l1!=null || l2!=null || jin > 0) {
            int sum = jin;
            if(l1!= null) sum += l1.val;
            if(l2!= null) sum += l2.val;
            jin = sum/10;
            ans.next = new ListNode(sum%10);
            ans = ans.next;
            if(l1!=null)l1 = l1.next;
            if(l2!=null)l2 = l2.next;
        }
        return get(dummy.next);
    }

    ListNode get(ListNode node) {
        ListNode dummy = new ListNode(-1,null);//前一个节点
        while(node != null) {
            ListNode nodenext = node.next;
            node.next = dummy.next;
            dummy.next = node;
            node = nodenext;
        }
        return dummy.next;
    }
}

复杂度分析

• 时间复杂度：O(max(m,n))，m/n分别为两个链表的长度,反转和相加都时O(max(m,n))。
• 空间复杂度：O(1)。

栈

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        //考虑不反转 直接使用数组保存
        int[] arr1 = get(l1),arr2 = get(l2);
        int[] arr3 = new int[Math.max(arr1.length,arr2.length)+1];
        int len1 = arr1.length, len2 = arr2.length;
        int jin = 0;
        ListNode dummy = new ListNode();
        while(len1 > 0 || len2 > 0 || jin > 0) {
            int sum = jin;
            if(len1 > 0) sum += arr1[--len1];
            if(len2 > 0) sum += arr2[--len2];
            jin = sum/10;
            //反向创建
            ListNode node = new ListNode(sum%10);
            node.next = dummy.next;
            dummy.next = node;
        }
        return dummy.next;
    }

    int[] get(ListNode node) {
        int len = 0;
        for(ListNode tmp=node;tmp!=null;len++,tmp=tmp.next);
        int[] res = new int[len];
        int i = 0;
        for(ListNode tmp=node;tmp!=null;res[i++]=tmp.val,tmp=tmp.next);
        return res;
    }
}

复杂度分析

• 时间复杂度：O(max(m,n))，遍历链表和相加都需要O(m)/O(n)。
• 空间复杂度：O(m+n)，即数组栈空间。

2023.07.03