leetcode-2-Add-Two-Numbers

发表于   |  

描述

You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

Input:(2 -> 4 -> 3) + (5 -> 6 -> 4)
Output:7 -> 0 -> 8

分析

刚看这题的时候还以为是反方向的，看了半天，原来就跟普通加法的算法一样，直接相加，用一个变量记录进位即可，需要注意边界情况。

解决方案1（Python）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# 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: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        result = current = ListNode()
        remainder = 0
        
        while l1 or l2:
            x = l1.val if l1 else 0
            y = l2.val if l2 else 0
            
            total = x + y + remainder
            current.next = ListNode(total % 10)
            remainder = total // 10
            if l1:
                l1 = l1.next
            if l2:
                l2 = l2.next
            current = current.next
        if remainder:
            current.next = ListNode(remainder)
        return result.next

解决方案2(C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* dummy = new ListNode(0);
        ListNode *p = dummy;
        int carry = 0;
        
        while(l1 || l2 || carry) {
            if(l1) {
                carry += l1->val;
                l1 = l1->next;
            }
            if(l2) {
                carry += l2->val;
                l2 = l2->next;
            }
            p->next = new ListNode(carry % 10);
            carry /= 10;
            p = p->next;
        }
        return dummy->next;
    }
};

解决方案3(Golang)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    head := &ListNode{}
    res := head
    
    carry, sum := 0, 0
    
    for l1 != nil || l2 != nil || carry != 0 {
        head.Next = &ListNode{}
        head = head.Next
        
        sum = carry
        if l1 != nil {
            sum += l1.Val
            l1 = l1.Next
        }
        if l2 != nil {
            sum += l2.Val
            l2 = l2.Next
        }
        head.Val, carry = sum%10, sum/10
    }
    
    return res.Next
}

解决方案4(Javascript)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/**
 * 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) {
    var dummy = new ListNode(0);
    var p = dummy;
    var carry = 0;
    
    while (l1 !== null || l2 !== null || carry > 0) {
        if (l1 !== null) {
            carry += l1.val;
            l1 = l1.next;
        }
        if (l2 !== null) {
            carry += l2.val;
            l2 = l2.next;
        }
        p.next = new ListNode(carry % 10);
        carry = Math.floor(carry/10);
        p = p.next;
    }
    return dummy.next;
};

解决方案5(Rust)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
// Definition for singly-linked list.
// #[derive(PartialEq, Eq, 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 l1_unwrap = l1.unwrap();
        let mut l2_unwrap = l2.unwrap();
        let mut dummy = ListNode::new(0);
        
        let mut res = Solution::make_node(l1_unwrap.val + l2_unwrap.val);
        dummy.next.get_or_insert(Box::new(res.0));
        
        let mut p = &mut dummy.next;
        
        while l1_unwrap.next.is_some() || l2_unwrap.next.is_some() {
            match p {
                None => break,
                Some(now) => {
                    l1_unwrap = l1_unwrap.next.or(Some(Box::new(ListNode::new(0)))).unwrap();
                    l2_unwrap = l2_unwrap.next.or(Some(Box::new(ListNode::new(0)))).unwrap();
                    res = Solution::make_node(l1_unwrap.val + l2_unwrap.val + res.1);
                    now.next.get_or_insert(Box::new(res.0));
                    p = &mut now.next;
                }
            }
        }
        
        if res.1 > 0 {
            if let Some(now) = p {
                now.next.get_or_insert(Box::new(ListNode::new(res.1)));
            }
        }
        dummy.next
        
    }
    
    fn make_node(mut result: i32) -> (ListNode, i32) {
        let carry;
        if result > 9 {
            carry = 1;
            result = result - 10;
        } else {
            carry = 0;
        }
        (ListNode::new(result), carry)
    }
}

相关问题

题目来源