两数相加

[PisecesPeng]

两数相加

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

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

题目地址: https://leetcode-cn.com/problems/add-two-numbers/

[PisecesPeng]

解题思路

• 遍历两个链表, 同下标的进行相加, 且仅保留一位数(判断是否进位),
• 若两个链表的长度不一样, 则将未操作的链表元素直接放置在结果最后.

代码

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

private static ListNode func(ListNode l1, ListNode l2) {
    ListNode result = new ListNode(0);
    boolean isCarry = false;  // 进位标识
    // 判断是否存在listNode, 并开始循环
    boolean l1IsNull = Objects.nonNull(l1), l2IsNull = Objects.nonNull(l2);
    while (l1IsNull || l2IsNull) {
        int tmpVal = 0;
        // 判断listNode是否还存在
        if (l1IsNull) {
            tmpVal += l1.val;
            l1IsNull = Objects.nonNull(l1 = l1.next);
        }
        if (l2IsNull) {
            tmpVal += l2.val;
            l2IsNull = Objects.nonNull(l2 = l2.next);
        }
        // 判断是否需要进位
        if (isCarry) {
            tmpVal += 1;
            isCarry = false;
        }
        // 判断本次循环之和是否需要进位
        if (tmpVal / 10 > 0) isCarry = true;
        // 获得最后一个listNode, 然后在其.next添加新listNode
        lastNode(result).next = new ListNode(tmpVal % 10);
    }
    // 判断是否还存在进位
    if (isCarry) lastNode(result).next = new ListNode(1);
    return result.next;
}

// 找出最后一个ListNode
private static ListNode lastNode(ListNode listNode) {
    if (Objects.isNull(listNode.next)) {
        return listNode;
    } else {
        return lastNode(listNode.next);
    }
}

[PisecesPeng]

LeetCode题解

解题思路

• 同时遍历两个数组, 计算它们的和, 并与当前位置的进位值相加,
• 注意, '长度不同'或'存在有进位'时, 需要附加到节点之后.

代码

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

public static ListNode func(ListNode l1, ListNode l2) {
    ListNode head = null, tail = null;
    int carry = 0;
    while (l1 != null || l2 != null) {
        int n1 = l1 != null ? l1.val : 0;
        int n2 = l2 != null ? l2.val : 0;
        int sum = n1 + n2 + carry;
        if (head == null) {
            head = tail = new ListNode(sum % 10);
        } else {
            tail.next = new ListNode(sum % 10);
            tail = tail.next;
        }
        carry = sum / 10;
        if (l1 != null) {
            l1 = l1.next;
        }
        if (l2 != null) {
            l2 = l2.next;
        }
    }
    if (carry > 0) {
        tail.next = new ListNode(carry);
    }
    return head;
}