两数相加

原题链接

使用的方法

• 模拟：通过模拟两个链表的加法过程，逐位相加并处理进位，最终得到结果链表。

解题思路

• 首先，创建一个虚拟头节点 dummy，用于构建结果链表。初始化一个指针 current 指向 dummy，以及一个变量 carry 用于存储进位。
• 然后，使用一个循环遍历两个链表，直到两个链表都遍历完且没有进位。对于每一位，从两个链表中获取当前节点的值，如果当前节点为空，则值为0。计算当前位的和 sum，并更新进位 carry。
• 接下来，将当前位的结果（sum % 10）创建一个新的节点，并将其连接到结果链表的末尾。然后将 current 指针移动到新节点。
• 最后，返回结果链表的头节点，即 dummy.next。

代码实现

/**
 * Definition for singly-linked list.
 * 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; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode current = dummy;
        int carry = 0;
        while(l1 != null || l2 != null || carry != 0){
            int val1 = l1 != null ? l1.val:0;
            int val2 = l2 != null ? l2.val:0;

            int sum = val1 + val2 + carry;
            carry = sum/10;
            int digit = sum%10;
            
            current.next = new ListNode(digit);
            current = current.next;

            if(l1 != null)
                l1 = l1.next;
            if(l2 != null)
                l2 = l2.next;
        }
        return dummy.next;
    }
}