两数相加(链表版)

Tips

题目类型: LinkedList

题目

两个非空的链表, 表示两个非负的整数. 它们每位数字都是按照逆序的方式存储的, 并且每个节点只能存储一位数字. 将两个数相加, 并以相同形式返回一个表示和的链表, 两个链表都不会以 0 开头.

提示:

• 每个链表中的节点数在范围 [1, 100] 内
• 0 <= Node.val <= 9
• 题目数据保证列表表示的数字不含前导零

示例

输入: l1 = 2 -> 4 -> 3, l2 = 5 -> 6 -> 8

输出: 7 -> 0 -> 2 -> 1

解释: 342 + 865 = 1207

题解

JavaScript

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var addTwoNumbers = function (l1, l2) {
  const dummy = new ListNode(null)
  let curr = dummy
  let carry = 0

  // 将 l1 和 l2 都走到头
  while (l1 || l2) {
    const a = l1 ? l1.val : 0
    const b = l2 ? l2.val : 0
    const sum = a + b + carry

    carry = (sum / 10) | 0
    curr.next = new ListNode(sum % 10)

    if (l1) l1 = l1.next
    if (l2) l2 = l2.next
    curr = curr.next
  }

  // 如果最后 carry === 1, 说明还需要加上一位(最高位)
  if (carry) curr.next = new ListNode(1)

  return dummy.next
}

Rust

// Definition for singly-linked list.
// #[derive(PartialEq, Eq, Clone, Debug)]
// pub struct ListNode {
//   pub val: i32,
//   pub next: Option<Box<ListNode>>
// }
//
// impl ListNode {
//   #[inline]
//   fn new(val: i32) -> Self {
//     ListNode {
//       next: None,
//       val
//     }
//   }
// }
pub fn add_two_numbers(
    l1: Option<Box<ListNode>>,
    l2: Option<Box<ListNode>>,
) -> Option<Box<ListNode>> {
    let mut dummy_head = ListNode::new(0);
    let mut curr = &mut dummy_head;
    let mut carry = 0;
    let mut l1 = l1;
    let mut l2 = l2;

    while l1.is_some() || l2.is_some() || carry != 0 {
        let mut sum = carry;
        
        if let Some(node) = l1 {
            sum += node.val;
            l1 = node.next;
        }
        if let Some(node) = l2 {
            sum += node.val;
            l2 = node.next;
        }

        carry = sum / 10;
        curr.next = Some(Box::new(ListNode::new(sum % 10)));
        curr = curr.next.as_mut().unwrap();
    }

    dummy_head.next
}