2. 两数相加

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807

解题思路

遍历两个链表，每一步根据两个链表的值新建一个节点，同时要注意进位和两个链表长度不一样的情况

/**
 * 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}
 */
const addTwoNumbers = function(l1, l2) {
    let addOne = 0
    let dummy = new ListNode(-1)
    let head = dummy
    let temp = 0
    while(l1 || l2){
        let n1=n2 = 0
      if(l1 !== null){
          n1 = l1.val
        l1 = l1.next
      }
      if(l2 !== null){
          n2 = l2.val
        l2 = l2.next
      }
      temp = n1+n2+addOne
      addOne = Math.floor(temp/10)
      temp = temp%10
      dummy.next = new ListNode(temp)
      dummy = dummy.next
    }
      if(addOne===1){
        dummy.next = new ListNode(1)
    }
      return head.next
};

Go

复习语法：链表应该使用引用，以及ListNode.Next也应该使用引用。

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    addOne := 0
    dummy := &ListNode{Val:-1}
    head := dummy
    for l1!=nil || l2!=nil{
        n1,n2 := 0,0
        if l1 != nil{
            n1 = l1.Val
            l1 = l1.Next
        }
        if l2 != nil{
            n2 = l2.Val
            l2 = l2.Next
        }
        temp := n1+n2+addOne
        temp,addOne = temp%10,temp/10
        dummy.Next = &ListNode{Val:temp}
        dummy = dummy.Next
    }
    if addOne>=1{
        dummy.Next = &ListNode{Val:1}
    }
    return head.Next
}

Rust

这道题充分体现了Rust和上面两种语言的不同。首先链表的储存类型是Option>因为Rust无法确定链表类型的大小，只能使用Box的引用。由于使用的是Option，所以要使用match才能把其中的ListNode取出来进行取值和next。使用循环可以使用loop知道两个链表都便利完成以及进位也为零，而在对dummy进行赋值的时候需要先解引用。

// 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
//     }
//   }
// }
impl Solution {
    pub fn add_two_numbers(l1: Option<Box<ListNode>>, l2: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
        let mut head = None;
        let mut dummy = &mut head;
        //这时head和dummy都指向None同一块内存地址
        let mut t = (l1,l2,0,0); // list1 list2 temp addOne

        loop{
            t = match t {
                (None,None,_,0) => break,
                (None,None,_,addOne) => (None,None,addOne,0),
                (Some(list),None,_,addOne) | (None,Some(list),_,addOne) => (list.next,None,(list.val+addOne)%10,(list.val+addOne)/10),
                (Some(list1),Some(list2),_,addOne) => (list1.next,list2.next,(list1.val+list2.val+addOne)%10,(list1.val+list2.val+addOne)/10),
            };
            *dummy = Some(Box::new(ListNode::new(t.2)));
            dummy = &mut dummy.as_mut().unwrap().next;
        };
        head
    }
}