小学生都能看懂的题解 | #链表相加(二)#

问题描述

假设你有两个数字串，比如 937 和 63。但是这些数字不是写在纸上，而是用小珠子串成的项链。项链的开头是数字的最高位，结尾是最低位。我们的任务是把这些数字串相加，并且把结果也做成一个项链。

解释步骤

1. 反转项链：为了让计算更容易，我们先把项链倒过来，这样从项链的开头开始就是最低位了。
2. 逐位相加：从项链的开头开始，每次拿一个珠子相加，如果加起来超过 9，就记得进位。
3. 记录结果：每次加完之后，把结果放在新的项链上。
4. 再次反转：最后，把结果项链再倒回来，让它从最高位开始。

代码实现

下面是一个简单的 Java 代码实现

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

// 反转链表的方法
public ListNode reverseList(ListNode head) {
    ListNode prev = null; // 前一个节点
    ListNode curr = head; // 当前节点
    while (curr != null) {
        ListNode next = curr.next; // 记录下一个节点
        curr.next = prev; // 把当前节点指向前一个节点
        prev = curr; // 移动前一个节点的位置
        curr = next; // 移动当前节点的位置
    }
    return prev; // 返回反转后的头节点
}

// 加法方法
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    // 先反转两个链表
    l1 = reverseList(l1);
    l2 = reverseList(l2);

    ListNode dummyHead = new ListNode(0); // 创建一个虚拟头节点
    ListNode curr = dummyHead; // 指向虚拟头节点
    int carry = 0; // 进位标志

    // 遍历两个链表
    while (l1 != null || l2 != null || carry != 0) {
        int val1 = (l1 != null) ? l1.val : 0; // 如果 l1 不为空，取 l1 的值，否则为 0
        int val2 = (l2 != null) ? l2.val : 0; // 同上
        int sum = val1 + val2 + carry; // 相加并考虑进位
        
        // 更新进位
        carry = sum / 10;
        // 新建节点并放入结果链表
        curr.next = new ListNode(sum % 10);
        curr = curr.next; // 移动当前节点
        
        if (l1 != null) l1 = l1.next; // 移动 l1
        if (l2 != null) l2 = l2.next; // 移动 l2
    }

    // 再次反转结果链表
    return reverseList(dummyHead.next);
}

这段代码会生成一个新链表，代表 937 + 63 的结果。结果链表将是 1->0->0->0

如果这篇文章对你有帮助，请点个免费的赞👍，让它帮助更多的人。