LeetCode：Add Two Numbers

刺骨的言语ヽ痛彻心扉 2022-07-12 07:42 84阅读 0赞

leetcode的第二题，把两个整数表示成两个链表，链表表示顺序和整数的顺序反过来，其实可以转换成两个整数相加，但是万一是大数呢。

我的思路就是使用的是python的链表表示两个整数，然后把低位相加，再和剩余的高位拼接起来，中间只要注意一下进位的问题，应该不算难。

可是偏偏leetcode已经预先定义好了链表的节点结构，不能直接使用python自己的链表计算。我因为是第一次做leetcode的题目，所以在输入和输出的转换上浪费了很多时间，希望后来的朋友能注意一下这个地方。看来不是所有的题目，用python写都是最优的，我太天真了。

不多说了，上代码。

#! /usr/bin/env python
        # -*- coding:utf8 -*-
    
        """ leetcode 2: Add Two Numbers """
    
        import os
        import sys
        import time
    
        # 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 """
                ll1 = []
                ll2 = []
                while (l1.next != None):
                    ll1.append(l1.val)
                    l1 = l1.next
                ll1.append(l1.val)
                while (l2.next != None):
                    ll2.append(l2.val)
                    l2 = l2.next
                ll2.append(l2.val)
                min_len = 0
                lt = []
                if len(ll1) >= len(ll2):
                    min_len = len(ll2)
                else:
                    min_len = len(ll1)
                incre_flag = 0
                for i in range(0, min_len):
                    tmp_sum = ll1[i] + ll2[i] + incre_flag
                    incre_flag = 0
                    if tmp_sum < 10:
                        lt.append(tmp_sum)
                    else:
                        incre_flag = 1
                        lt.append(tmp_sum % 10)
                if min_len < len(ll1):
                    for i in range(min_len, len(ll1)):
                        tmp_sum = ll1[i] + incre_flag
                        incre_flag = 0
                        if tmp_sum < 10:
                            lt.append(tmp_sum)
                        else:
                            incre_flag = 1
                            lt.append(tmp_sum % 10)
                else:
                    for i in range(min_len, len(ll2)):
                        tmp_sum = ll2[i] + incre_flag
                        incre_flag = 0
                        if tmp_sum < 10:
                            lt.append(tmp_sum)
                        else:
                            incre_flag = 1
                            lt.append(tmp_sum % 10)
                if incre_flag == 1:
                    lt.append(incre_flag)
                n = None
                for i in range(len(lt) - 1, -1, -1):
                    ret_l = ListNode(0)
                    ret_l.val = lt[i]
                    if n != None:
                        ret_l.next = n
                    else:
                        ret_l.next = None
                    n = ret_l
                return ret_l
    
    
        if __name__ == "__main__":
            n1 = ListNode(4)
            n2 = ListNode(5)
            n3 = ListNode(5)
            n4 = ListNode(5)
            n2.next = n1
            n3.next = n2
            n4.next = n3
            l1 = n2
            l2 = n4
    
            s = Solution()
            l3 = s.addTwoNumbers(l1, l2)
            while l3.next != None:
                sys.stdout.write("%s->" % (l3.val))
                l3 = l3.next
            sys.stdout.write("%s\" % (l3.val))