LeetCode第二题：两数相加

题目

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

说明

如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/add-two-numbers

解题思路

此题其实就是简单的把两个链表，从左至右相加而已，相当于一个特殊的加法运算

1. 从左至右将两个链表上的每一位的数字相加
2. 判断相加后的值是否需要进位
3. 返回最初声明的数组

不需要声明新链表的写法：

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

public static ListNode addList(ListNode l1, ListNode l2) {
        ListNode node = l1;
        boolean addBit = false;
        // 判断是否还有可以相加的元素
        while (node != null) {
            // 如果l2不为空
            if (l2 != null) {
                // 计算val
                int num = node.val + l2.val;
                if (addBit) {
                    num++;
                    addBit = false;
                }
                // 计算进位标记
                if (num > 9) {
                    addBit = true;
                    node.val = num - 10;
                } else {
                    node.val = num;
                }
                // 设置新的node
                if (node.next != null) {
                    node = node.next;
                    l2 = l2.next;
                } else if (l2.next != null) {
                // 如果node比l2短，就让next指向l2的下一个元素,l2指向null
                    node.next = l2.next;
                    node = node.next;
                    l2 =  null;
                } else {
                // 如果都为空
                        node.next = new ListNode(1);
                    break;
                }
            // 如果l2为空
            } else {
                // 计算进位标记
                if (addBit) {
                    if (node.val == 9) {
                        node.val = 0;
                    } else {
                        node.val++;
                        addBit = false;
                    }
                }
                // 判断是否为还有没有处理完的元素
                if (node.next == null) {
                    if (addBit) {
                        node.next = new ListNode(1);
                    }
                    break;
                }
                node = node.next;
            }
        }
        return l1;
}

声明新链表的写法

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode node = new ListNode(0);
        ListNode returnNode = node;
        boolean addBit = false;
        while (l1 != null || l2 != null) {
            int val1 = l1 != null ? l1.val : 0;
            int val2 = l2 != null ? l2.val : 0;
            int tempVal = val1 + val2;
            if (addBit) {
                tempVal++;
                addBit = false;
            }
            if (tempVal > 9) {
                tempVal = tempVal - 10;
                addBit = true;
            }
            l1 = l1 != null ? l1.next : null;
            l2 = l2 != null ? l2.next : null;
            node.next = new ListNode(tempVal);
            node = node.next;
        }
        if (addBit) {
            node.next = new ListNode(1);
        }
        return returnNode.next;
    }
}

其他语言解法

1. JS

var addTwoNumbers = function (l1, l2) {
    var node = new ListNode(null);
    var result = node;
    var enter = 0;
    while (l1 || l2) {
        var sum = (l1 ? l1.val : 0) + (l2 ? l2.val : 0) + enter;
        if (sum >= 10) {
            enter = 1;
            sum = sum - 10;
        } else {
            enter = 0;
        }
        node = node.next = new ListNode(sum);
        if(l1) l1=l1.next;
        if(l2) l2=l2.next;
    }
    if (enter === 1) {
        node.next = new ListNode(1);
    }
    return result.next;
};

2. Python

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


class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        add_bit = False
        node = l1
        while l1 is not None:
            if l2 is not None:
                temp_val = l1.val + l2.val
                if add_bit:
                    temp_val = temp_val + 1
                    add_bit = False
                if temp_val > 9:
                    temp_val = temp_val - 10
                    add_bit = True
                l1.val = temp_val
                if l1.next is not None:
                    l1 = l1.next
                    l2 = l2.next
                elif l2.next is not None:
                    l1.next = l2.next
                    l1 = l1.next
                    l2 = None
                else:
                    break
            else:
                temp_val = l1.val
                if add_bit:
                    temp_val = temp_val + 1
                    add_bit = False
                if temp_val > 9:
                    temp_val = temp_val - 10
                    add_bit = True
                l1.val = temp_val
                if l1.next is None:
                    break
                else:
                    l1 = l1.next
        if add_bit:
            l1.next = ListNode(1)
        return node

点击查看更多源码

直通车

LeetCode第二题直达车

我的个人博客,有空来坐坐