445.两数相加II

链接：445.两数相加II
难度：Medium
标签：栈、链表、数学
简介：给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。

题解 1 - javascript

• 编辑时间：2020-04-14
• 执行用时：140ms
• 内存消耗：38.6MB
• 编程语言：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) {
  let res;
  const arr1 = [];
  while (true) {
    arr1.push(l1);
    if (l1.next === null) break;
    l1 = l1.next;
  }
  const arr2 = [];
  while (true) {
    arr2.push(l2);
    if (l2.next === null) break;
    l2 = l2.next;
  }
  let f = false;
  while (arr1.length !== 0 && arr2.length !== 0) {
    let num = arr1.pop().val + arr2.pop().val;
    if (f) num++;
    if (num >= 10) {
      num = num - 10;
      f = true;
    } else {
      f = false;
    }
    let temp = new ListNode(num);
    temp.next = res;
    res = temp;
  }
  while (arr1.length !== 0) {
    let temp = arr1.pop();
    if (f) {
      temp.val++;
      if (temp.val >= 10) temp.val = temp.val - 10;
      else f = false;
    }
    temp.next = res;
    res = temp;
  }
  while (arr2.length !== 0) {
    let temp = arr2.pop();
    if (f) {
      temp.val++;
      if (temp.val >= 10) temp.val = temp.val - 10;
      else f = false;
    }
    temp.next = res;
    res = temp;
  }
  if (f) {
    let temp = new ListNode(1);
    temp.next = res;
    res = temp;
  }
  return res;
};

题解 2 - cpp

• 编辑时间：2023-07-03
• 执行用时：24ms
• 内存消耗：68.9MB
• 编程语言：cpp
• 解法介绍：递归。

class Solution {
public:
    int get_len(ListNode *l) {
        int cnt = 0;
        for (ListNode *p = l; p; p = p->next) cnt++;
        return cnt;
    }
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        int len1 = get_len(l1), len2 = get_len(l2);
        if (len2 > len1) {
            swap(len1, len2);
            swap(l1, l2);
        }
        while (len1 > len2) {
            ListNode *head = new ListNode(0, l2);
            l2 = head;
            len2++;
        }
        auto res = dfs(l1, l2);
        if (res.first) {
            ListNode *head = new ListNode(1, l1);
            l1 = head;
        }
        return l1;
    }
    pair<int, ListNode*> dfs(ListNode* l1, ListNode* l2) {
        if (!l1) return make_pair(0, l2);
        if (!l2) return make_pair(0, l1);
        auto res = dfs(l1->next, l2->next);
        l1->next = res.second;
        l1->val += l2->val + res.first;
        int add = 0;
        if (l1->val >= 10) {
            l1->val -= 10;
            add = 1;
        }
        return make_pair(add, l1);
    }
};

题解 3 - python

• 编辑时间：2023-07-03
• 执行用时：88ms
• 内存消耗：15.9MB
• 编程语言：python
• 解法介绍：同上。

def getLen(l: Optional[ListNode]):
    if not l:
        return 0
    cnt = 0
    while l:
        cnt += 1
        l = l.next
    return cnt

def dfs(l1: Optional[ListNode], l2: Optional[ListNode]) -> Tuple[int, ListNode]:
    if not l1:
        return (0, l2)
    if not l2:
        return (0, l1)
    add, next = dfs(l1.next, l2.next)
    l1.next = next
    l1.val += l2.val + add
    add = 0
    if l1.val >= 10:
        l1.val -= 10
        add = 1
    return (add, l1)
class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        len1, len2 = getLen(l1), getLen(l2)
        if len2 > len1:
            len1, len2 = len2, len1
            l1, l2 = l2, l1
        while len1 > len2:
            head = ListNode(0, l2)
            l2 = head
            len2 += 1
        add, node = dfs(l1, l2)
        if add:
            head = ListNode(1, l1)
            l1 = head
        return l1

题解 4 - rust

• 编辑时间：2023-07-03
• 内存消耗：1.9MB
• 编程语言：rust
• 解法介绍：同上。

fn get_len(l: &Option<Box<ListNode>>) -> usize {
    match l {
        Some(ref node) => get_len(&node.next) + 1,
        None => 0,
    }
}
fn dfs(
    mut l1: Option<Box<ListNode>>,
    mut l2: Option<Box<ListNode>>,
) -> (i32, Option<Box<ListNode>>) {
    if l1.is_none() {
        (0, l2)
    } else if l2.is_none() {
        (0, l1)
    } else {
        let node1 = l1.as_mut().unwrap();
        let node2 = l2.as_mut().unwrap();
        let (mut add, next) = dfs(node1.next.take(), node2.next.take());
        node1.val += node2.val + add;
        node1.next = next;
        add = 0;
        if node1.val >= 10 {
            node1.val -= 10;
            add = 1;
        }
        (add, l1)
    }
}
impl Solution {
    pub fn add_two_numbers(
        mut l1: Option<Box<ListNode>>,
        mut l2: Option<Box<ListNode>>,
    ) -> Option<Box<ListNode>> {
        let (mut len1, mut len2) = (get_len(&l1), get_len(&l2));
        if len2 > len1 {
            std::mem::swap(&mut len1, &mut len2);
            std::mem::swap(&mut l1, &mut l2);
        }
        while len1 > len2 {
            let mut head = Box::new(ListNode::new(0));
            head.next = l2.take();
            l2 = Some(head);
            len2 += 1;
        }
        let (add, mut node) = dfs(l1, l2);
        if add != 0 {
            let mut head = Box::new(ListNode::new(1));
            let next = node.take();
            head.next = next;
            node = Some(head);
        }
        node
    }
}