LeetCode：两数相加

两数相加

题目描述

给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序 的方式存储的，并且每个节点只能存储一位数字。

链表结构

public class ListNode {
    int val;
    ListNode next;
    ListNode() {
    }
    ListNode(int val) {
        this.val = val;
    }
    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

解题思路

两个链表分为存储了两个数，存储方式为按照逆序存储。

即每个链表的头部节点，即为每个数的个位数。

而两个数相加，正好是从个位数开始相加。

所以我们可以遍历两个链表，对每个链表节点的数进行相加操作，将相加出来的结果存储在一个链表中即可。

注意点

• 进位：两个数相加，相加结果可能会发生进位，可以通过 / 运算符获取进位值，通过 % 运算符获取当前位值。

• 高位不足：两个数相加，如果两个数的位数不一致，位数小的可能会发生高位不足的情况，这时可以使用 0 补足。

• 值为null：如果两个相加的数链表中有一个值为 null ，则需要注意。

解题代码

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode dummyHead = new ListNode(0);//虚拟头部
    ListNode p = dummyHead;
    ListNode p1 = l1, p2 = l2;
    // 进位
    int carry = 0;
    // 两个节点相加的值
    int sum = 0;
    // l1,l2任一链表未到尾部，或者进位不为0都要继续
    while (p1 != null || p2 != null || carry > 0) {
        // 如果一个列表已经到尾部，则值用0代替
        sum = (p1 == null ? 0 : p1.val) + (p2 == null ? 0 : p2.val) + carry;
        // 判断sum是否有进位
        carry = sum / 10;
        // 创建新节点，并将头结点指向该节点
        p.next = new ListNode(sum % 10);
        // 移动两个链表
        p1 = p1 == null ? null : p1.next;
        p2 = p2 == null ? null : p2.next;
        // 移动头节点
        p = p.next;
    }
    // 返回除去头部节点之外的链表结构
    // 这样返回还直接避免了相加的两个参数值为null的情况
    return dummyHead.next;
}