LeetCode 445. Add Two Numbers II

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

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

进阶:

如果输入链表不能修改该如何处理？换句话说，你不能对列表中的节点进行翻转。

示例:

输入: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
输出: 7 -> 8 -> 0 -> 7

思路:

1. 毫无疑问,难点在于进位的处理,不需要进位的情况下,仅仅只是简单的同位相加
2. 由于链表无法逆向遍历,需要通过其他手段辅助定位,如:链表反转,集合. 也可以通过转为10进制进行操作,不过这也是效率较低的选择(注意溢出)
3. 在不知晓链表长度情况下,重建链表的效果要高于在原立案表上进行改动

代码1:

public ListNode addTwoNumbers1(ListNode l1, ListNode l2) {
        if (l1 == null || l2 == null)
            return l1;
        ListNode temp = l1, cur;
        long num1 = 0, num2 = 0;
        //转为十进制数
        while (temp != null) {
            num1 = num1 * 10 + temp.val;
            temp = temp.next;
        }
        temp = l2;
        while (temp != null) {
            num2 = num2 * 10 + temp.val;
            temp = temp.next;
        }
        //求和并重构链表
        num1 = num1 + num2;
        if (num1 > 0) {
            ListNode res = new ListNode(0);
            res.next = temp;
            int k;
            while (num1 != 0) {
                k = (int) (num1 % 10);
                cur = res.next;
                temp = new ListNode(k);
                res.next = temp;
                temp.next = cur;
                num1 = num1 / 10;
            }
        } else {
            temp = new ListNode(0);
        }
        return temp;
    }

分析:

• 将链表转为十进制,自动进位进位处理,思路非常简单
• 测试用例中有许多越界数组,该方法还需要添加溢出的处理,例如按位数用数组分批存储数字等

代码2

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        Stack<Integer> sta1 = new Stack<Integer>();
        Stack<Integer> sta2 = new Stack<Integer>();
        Stack<Integer> sta = new Stack<Integer>();
        //构建栈
        while (l1 != null) {
            sta1.push(l1.val);
            l1 = l1.next;
        }
        while (l2 != null) {
            sta2.push(l2.val);
            l2 = l2.next;
        }
        int c = 0;
        //相加进位,压入新栈
        while (!sta1.isEmpty() && !sta2.isEmpty()) {
            int sum = sta1.pop() + sta2.pop() + c;
            c = sum / 10;
            sum = sum % 10;
            sta.push(sum);
        }
        if (!sta2.isEmpty())
            sta1 = sta2;
        //为了应对两链表长度不同,另开一个循环进行处理
        while (!sta1.isEmpty()) {
            int sum = sta1.pop() + c;
            c = sum / 10;
            sum = sum % 10;
            sta.push(sum);
        }
        if (c == 1)
            sta.push(1);
        ListNode dump = new ListNode(0);
        ListNode ret = dump;
        while (!sta.isEmpty()) {
            dump.next = new ListNode((int) sta.pop());
            dump = dump.next;
        }
        return ret.next;
    }

分析:

• 使用栈进行操作,通过出栈操作达到逆向遍历链表的目的
• 此处也可以使用list等其他存储集合,但是效率都很低

代码3:

    public ListNode addTwoNumbersBest(ListNode l1, ListNode l2) {
        ListNode root1 = exec(l1);
        ListNode root2 = exec(l2);
        
        ListNode root = null, current = null;
        int bits = 0;
        ListNode n1 = root1, n2 = root2;
        for(;n1 != null && n2 != null;n1 = n1.next, n2 = n2.next) {
            int value = n1.val + n2.val + bits;
            bits = value / 10;
            
            if(root == null) {
                root = new ListNode(value % 10);
                current = root;
            }else {
                current.next = new ListNode(value % 10);
                current = current.next;
            }
        }
        
        for(;n1 != null;n1 = n1.next) {
            int value = n1.val + bits;
            bits = value / 10;
            
            current.next = new ListNode(value % 10);
            current = current.next;
        }
        
        for(;n2 != null;n2 = n2.next) {
            int value = n2.val + bits;
            bits = value / 10;
            
            current.next = new ListNode(value % 10);
            current = current.next;
        }
        
        if(bits != 0) {
            current.next = new ListNode(bits);
            current = current.next;
        }
        return exec(root);
    }
    //反转方法
    public ListNode exec(ListNode root) {
        ListNode node = root, previous = null;
        while(node != null) {
            ListNode next = node.next;
            node.next = previous;
            previous = node;
            node = next;
        }
        return previous;
    }

分析:

• 执行效率分布中非常靠前的方法
• 先反转链表,使其可以逆向遍历,之后使用相同的处理方式,计算和值

总结:

1. 本题主要考察当顺序遍历无法满足结题要求时,对数据的处理方法
2. 逆向链表与栈都是非常好的方法,若使用转为十进制进行操作,需要处理数值溢出问题