leet code -- 两数相加

LeetCode原题

输入 (2->4_->3) + (5->6->4) = (7->0->8)

问题描述:给定两个链表分别代表两个非负整数,链表的每个结点分别存储整数的每位数字,且是逆序存储,即: 数字最低位存储在链表的表头,数字的最高位存储在链表的表尾。求解两个证书的和并以相同的链表形式返回计算的结果。

分析

  • 用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
26
27
28
29
30
31
32
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def addTwoNumbers(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
num1 = ""
num2 = ""
while l1:
num1 += str(l1.val)
l1 = l1.next
while l2:
num2 += str(l2.val)
l2 = l2.next
num1 = int(num1[::-1])
num2 = int(num2[::-1])
ans = str(num1 + num2)[::-1]
newlist = [int(ans[i]) for i in range(len(ans))]
# newlistnode = ListNode(0)
# for i in range(len(newlist) - 1):
# newlistnode.val = newlist[i]
# newlistnode.next = ListNode(newlist[i + 1])
# return newlistnode
return newlist

leetcode 截图,通过, 战胜16.85%, 看来还需要优化

  • 另一个做法就是逐个node相加,如果大于10就在下个node的value再加1,同样上代码

    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
    #include <iostream>
    using namespace std;
    struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x)
    :val(x), next(NULL)
    {}
    };
    class Solution {
    public:
    ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
    ListNode preHead(0), *p = &preHead;
    int carry = 0;
    while (l1 || l2 || carry) {
    int sum = (l1 ? l1->val : 0) + (l2 ? l2->val : 0) + carry;
    carry = sum / 10;
    p->next = new ListNode(sum % 10);
    p = p->next;
    l1 = l1 ? l1->next : l1;
    l2 = l2 ? l2->next : l2;
    }
    return preHead.next;
    }
    };
    int main() {
    Solution s;
    ListNode l01(2), l02(5), *l1 = &l01, *l2 = &l02;
    ListNode l11(4), l12(6);
    l1->next = &l11;
    l2->next = &l12;
    ListNode l21(3);
    ListNode l22(4);
    l1->next->next = &l21;
    l2->next->next = &l22;
    ListNode ll(0), *zjw = &ll;
    zjw = s.addTwoNumbers(l1, l2);
    while (zjw) {
    if (zjw->next)
    cout << zjw->val << " -> ";
    else
    cout << zjw->val << endl;
    zjw = zjw->next;
    }
    }

这里将链表写成一个类,并且对+号进行了重载,这样如果两个链表就可以直接相加了。

人艰不拆,生活不易