「力扣」第 2 题：两个数相加（中等）

「力扣」第 2 题：两个数相加（中等）

中文链接：2. 两数相加 ；

英文链接：2. Add Two Numbers 。

给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例：

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

思路：需要考虑的问题：

1、数字中是否有前置的 $0$（除了 $0$ 以外，没有前置的 $0$）；

2、负数是否考虑。

编码过程中需要思考的问题：

1、如何分别获得这个数组的个位、十位、百位、千位；

2、分别相加，如果大于 $10$，进一。

方法一：穿针引线

Java 代码：

class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
    }

    public ListNode(int[] nums) {
        this.val = nums[0];
        ListNode curNode = this;
        for (int i = 1; i < nums.length; i++) {
            curNode.next = new ListNode(nums[i]);
            curNode = curNode.next;
        }
    }

    @Override
    public String toString() {
        ListNode curNode = this;
        StringBuilder stringBuilder = new StringBuilder();
        while (curNode != null) {
            stringBuilder.append(curNode.val);
            stringBuilder.append(" -> ");
            curNode = curNode.next;
        }
        stringBuilder.append("NULL");
        return stringBuilder.toString();
    }
}


public class Solution {

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        // 特判
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }
        ListNode dummyNode = new ListNode(-1);
        ListNode curNode = dummyNode;
        int sum = 0;
        while (l1 != null || l2 != null) {
            if (l1 != null) {
                sum += l1.val;
                l1 = l1.next;
            }
            if (l2 != null) {
                sum += l2.val;
                l2 = l2.next;
            }
            curNode.next = new ListNode(sum % 10);
            sum /= 10;
            curNode = curNode.next;
        }
        if (sum == 1) {
            curNode.next = new ListNode(1);
        }
        return dummyNode.next;
    }

    public static void main(String[] args) {
        int[] nums1 = new int[]{5};
        int[] nums2 = new int[]{5};
        ListNode l1 = new ListNode(nums1);
        ListNode l2 = new ListNode(nums2);
        Solution solution = new Solution();
        ListNode addTwoNumbers = solution.addTwoNumbers(l1, l2);
        System.out.println(addTwoNumbers);
    }
}

Java 代码：

public class Solution {

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummyNode = new ListNode(-1);
        ListNode curNode = dummyNode;
        int carry = 0;
        while (l1 != null && l2 != null) {
            int val = l1.val + l2.val + carry;
            curNode.next = new ListNode(val % 10);
            carry = val / 10;
            curNode = curNode.next;
            l1 = l1.next;
            l2 = l2.next;
        }

        if (l1 == null) {
            curNode.next = l2;
        } else {
            curNode.next = l1;
        }

        if (carry == 1) {
            curNode.next = new ListNode(1);
        }
        return dummyNode.next;
    }
}

Python 代码：

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None


class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        if l1 is None:
            return l2

        if l2 is None:
            return l1

        dummy_node = ListNode(-1)
        cur_node = dummy_node
        s = 0

        # 只要二者之一非空，就加下去
        while l1 or l2:
            if l1:
                s += l1.val
                l1 = l1.next
            if l2:
                s += l2.val
                l2 = l2.next
            cur_node.next = ListNode(s % 10)
            s //= 10
            cur_node = cur_node.next
        if s == 1:
            cur_node.next = ListNode(1)
        return dummy_node.next

（本节完）