每日一题-两数相加 II

绝地灬酷狼 2023-07-25 12:37 8阅读 0赞

今天是2020年4月14日，星期二。

### 题目描述 ###

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

你可以假设除了数字 0 之外，这两个数字都不会以零开头。  
   
进阶：  
如果输入链表不能修改该如何处理？换句话说，你不能对列表中的节点进行翻转。  
   
示例：

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

### 题目思路 ###

看到这两个链表后，可以想到将每个链表转化为一个数字，进而将两个链表的相加转化为两个数字的加和。但在Java中存在一个问题，如果链表很长，可能转换为数字后，其范围大于了int最大的表示范围，甚至超过了long类型，此时就会出现问题，说明在大范围数据的时候不适用。后面借用了List去存储了链表中的数据，进行了求和，但是这个方法还是比较低效。

高效一些的方法则是可以借助栈的特性，遍历每个链表并加入栈中，则"高位"的数字位于栈底，最后相加；"低位"的数字位于栈顶，先相加。最后转换为结果需要的list即可。

### 参考代码 ###

*  自己写的低效代码

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
            int length1 = 0;
            int length2 = 0;
            ListNode tmp1 = l1;
            ListNode tmp2 = l2;
            List<Integer> value1List = new ArrayList<>();
            List<Integer> value2List = new ArrayList<>();
    
            while (tmp1 != null) {
                length1++;
                value1List.add(tmp1.val);
                tmp1 = tmp1.next;
            }
            while (tmp2 != null) {
                length2++;
                value2List.add(tmp2.val);
                tmp2 = tmp2.next;
            }
            int min = Math.min(length1, length2);
            int max = Math.max(length1, length2);
    
            List<Integer> list = new ArrayList<>();
            boolean isJinWei = false;
    
            int index = 0;
            if (min == length1) {
                for (int i = min - 1, j = max - 1; i >= 0; i--, j--) {
                    int current = value1List.get(i) + value2List.get(j);
                    if (isJinWei) {
                        current += 1;
                        isJinWei = false;
                    }
                    if (current >= 10) {
                        current -= 10;
                        isJinWei = true;
                    }
                    list.add(index, current);
                    index++;
                }
                for (int i = max - min - 1; i >= 0; i--) {
                    int current = value2List.get(i);
                    if (isJinWei) {
                        current++;
                        isJinWei = false;
                    }
                    if (current >= 10) {
                        current -= 10;
                        isJinWei = true;
                    }
                    list.add(index, current);
                    index++;
                }
                if (isJinWei) {
                    list.add(1);
                }
            } else {
                for (int i = min - 1, j = max - 1; i >= 0; i--, j--) {
                    int current = value1List.get(j) + value2List.get(i);
                    if (isJinWei) {
                        current += 1;
                        isJinWei = false;
                    }
                    if (current >= 10) {
                        current -= 10;
                        isJinWei = true;
                    }
                    list.add(index, current);
                    index++;
                }
                for (int i = max - min - 1; i >= 0; i--) {
                    int current = value1List.get(i);
                    if (isJinWei) {
                        current++;
                        isJinWei = false;
                    }
                    if (current >= 10) {
                        current -= 10;
                        isJinWei = true;
                    }
                    list.add(index, current);
                    index++;
                }
                if (isJinWei) {
                    list.add(1);
                }
            }
    
            ListNode head = new ListNode(-1);
            for (int i = 0; i < list.size(); i++) {
                ListNode node = new ListNode(list.get(i));
                node.next = head.next;
                head.next = node;
            }
    
            return head.next;
        }

*  参考甜姨的stack法的实例代码

/**
     * 使用栈的特性存储数据
     *
     * @param l1
     * @param l2
     * @return
     */
    public ListNode addTwoNumbers2(ListNode l1, ListNode l2) {
        Stack<Integer> stack1 = new Stack<>();
        Stack<Integer> stack2 = new Stack<>();
        while (l1 != null) {
            stack1.push(l1.val);
            l1 = l1.next;
        }
        while (l2 != null) {
            stack2.push(l2.val);
            l2 = l2.next;
        }
    
        int carry = 0;
        ListNode head = null;
        while (!stack1.isEmpty() || !stack2.isEmpty() || carry > 0) {
            int value1 = stack1.isEmpty() ? 0 : stack1.pop();
            int value2 = stack2.isEmpty() ? 0 : stack2.pop();
            int result = value1 + value2 + carry;
            ListNode node = new ListNode(result % 10);
            node.next = head;
            head = node;
            carry = result / 10;
        }
    
        return head;
    }