javascript 解法, 执行用时: 104 ms, 内存消耗: 45.6 MB, 提交时间: 2023-07-03 09:27:19

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var addTwoNumbers = function (l1, l2) {
    l1 = reverseList(l1);
    l2 = reverseList(l2); // l1 和 l2 反转后，就变成【2. 两数相加】了
    let l3 = addTwo(l1, l2);
    return reverseList(l3);
}

var reverseList = function (head) {
    if (head === null || head.next === null)
        return head;
    let newHead = reverseList(head.next);
    head.next.next = head; // 把下一个节点指向自己
    head.next = null; // 断开指向下一个节点的连接，保证最终链表的末尾节点的 next 是空节点
    return newHead;
};

// l1 和 l2 为当前遍历的节点，carry 为进位
var addTwo = function (l1, l2, carry = 0) {
    if (l1 === null && l2 === null) // 递归边界：l1 和 l2 都是空节点
        return carry ? new ListNode(carry) : null; // 如果进位了，就额外创建一个节点
    if (l1 === null) // 如果 l1 是空的，那么此时 l2 一定不是空节点
        [l1, l2] = [l2, l1]; // 交换 l1 与 l2，保证 l1 非空，从而简化代码
    carry += l1.val + (l2 ? l2.val : 0); // 节点值和进位加在一起
    l1.val = carry % 10; // 每个节点保存一个数位
    l1.next = addTwo(l1.next, (l2 ? l2.next : null), Math.floor(carry / 10)); // 进位
    return l1;
};

javascript 解法, 执行用时: 84 ms, 内存消耗: 46 MB, 提交时间: 2023-07-03 09:26:48

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
 var addTwoNumbers = function (l1, l2) {
    l1 = reverseList(l1);
    l2 = reverseList(l2);
    let l3 = addTwo(l1, l2);
    return reverseList(l3);
}
 
// 视频讲解 https://www.bilibili.com/video/BV1sd4y1x7KN/
var reverseList = function (head) {
    let pre = null;
    let cur = head;
    while (cur) {
        let nxt = cur.next;
        cur.next = pre;
        pre = cur;
        cur = nxt;
    }
    return pre;
};

var addTwo = function (l1, l2) {
    let dummy = new ListNode(); // 哨兵节点
    let cur = dummy;
    let carry = 0; // 进位
    while (l1 || l2 || carry) {
        if (l1) carry += l1.val; // 节点值和进位加在一起
        if (l2) carry += l2.val; // 节点值和进位加在一起
        cur = cur.next = new ListNode(carry % 10); // 每个节点保存一个数位
        carry = Math.floor(carry / 10); // 新的进位
        if (l1) l1 = l1.next; // 下一个节点
        if (l2) l2 = l2.next; // 下一个节点
    }
    return dummy.next; // 哨兵节点的下一个节点就是头节点
};

golang 解法, 执行用时: 8 ms, 内存消耗: 4.3 MB, 提交时间: 2023-07-03 09:26:01

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
// 视频讲解 https://www.bilibili.com/video/BV1sd4y1x7KN/
func reverseList(head *ListNode) *ListNode {
    var pre, cur *ListNode = nil, head
    for cur != nil {
        nxt := cur.Next
        cur.Next = pre
        pre = cur
        cur = nxt
    }
    return pre
}

func addTwo(l1, l2 *ListNode) *ListNode {
    dummy := &ListNode{} // 哨兵节点
    cur := dummy
    carry := 0 // 进位
    for l1 != nil || l2 != nil || carry != 0 { // 有一个不是空节点，或者还有进位，就继续迭代
        if l1 != nil {
            carry += l1.Val // 节点值和进位加在一起
        }
        if l2 != nil {
            carry += l2.Val // 节点值和进位加在一起
        }
        cur.Next = &ListNode{Val: carry % 10} // 每个节点保存一个数位
        carry /= 10 // 新的进位
        cur = cur.Next // 下一个节点
        if l1 != nil {
            l1 = l1.Next // 下一个节点
        }
        if l2 != nil {
            l2 = l2.Next // 下一个节点
        }
    }
    return dummy.Next // 哨兵节点的下一个节点就是头节点
}

func addTwoNumbers(l1, l2 *ListNode) *ListNode {
    l1 = reverseList(l1)
    l2 = reverseList(l2) // l1 和 l2 反转后，就变成【2. 两数相加】了
    l3 := addTwo(l1, l2)
    return reverseList(l3)
}

golang 解法, 执行用时: 4 ms, 内存消耗: 4.1 MB, 提交时间: 2023-07-03 09:25:32

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseList(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }
    newHead := reverseList(head.Next)
    head.Next.Next = head // 把下一个节点指向自己
    head.Next = nil // 断开指向下一个节点的连接，保证最终链表的末尾节点的 next 是空节点
    return newHead
}

// l1 和 l2 为当前遍历的节点，carry 为进位
func addTwo(l1, l2 *ListNode, carry int) *ListNode {
    if l1 == nil && l2 == nil { // 递归边界：l1 和 l2 都是空节点
        if carry != 0 {
            return &ListNode{Val: carry} // 如果进位了，就额外创建一个节点
        }
        return nil
    }
    if l1 == nil { // 如果 l1 是空的，那么此时 l2 一定不是空节点
        l1, l2 = l2, l1 // 交换 l1 与 l2，保证 l1 非空，从而简化代码
    }
    carry += l1.Val // 节点值和进位加在一起
    if l2 != nil {
        carry += l2.Val // 节点值和进位加在一起
        l2 = l2.Next    // 下一个节点
    }
    l1.Val = carry % 10 // 每个节点保存一个数位
    l1.Next = addTwo(l1.Next, l2, carry/10) // 进位
    return l1
}

func addTwoNumbers(l1, l2 *ListNode) *ListNode {
    l1 = reverseList(l1)
    l2 = reverseList(l2) // l1 和 l2 反转后，就变成【2. 两数相加】了
    l3 := addTwo(l1, l2, 0)
    return reverseList(l3)
}

java 解法, 执行用时: 2 ms, 内存消耗: 42 MB, 提交时间: 2022-11-23 16:54:05

/**
 * 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) {
        Deque<Integer> stack1 = new ArrayDeque<Integer>();
        Deque<Integer> stack2 = new ArrayDeque<Integer>();
        while (l1 != null) {
            stack1.push(l1.val);
            l1 = l1.next;
        }
        while (l2 != null) {
            stack2.push(l2.val);
            l2 = l2.next;
        }
        int carry = 0;
        ListNode ans = null;
        while (!stack1.isEmpty() || !stack2.isEmpty() || carry != 0) {
            int a = stack1.isEmpty() ? 0 : stack1.pop();
            int b = stack2.isEmpty() ? 0 : stack2.pop();
            int cur = a + b + carry;
            carry = cur / 10;
            cur %= 10;
            ListNode curnode = new ListNode(cur);
            curnode.next = ans;
            ans = curnode;
        }
        return ans;
    }
}

python3 解法, 执行用时: 64 ms, 内存消耗: 14.9 MB, 提交时间: 2022-11-23 16:53:34

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        s1, s2 = [], []
        while l1:
            s1.append(l1.val)
            l1 = l1.next
        while l2:
            s2.append(l2.val)
            l2 = l2.next
        ans = None
        carry = 0
        while s1 or s2 or carry != 0:
            a = 0 if not s1 else s1.pop()
            b = 0 if not s2 else s2.pop()
            cur = a + b + carry
            carry = cur // 10
            cur %= 10
            curnode = ListNode(cur)
            curnode.next = ans
            ans = curnode
        return ans