使用 python 完成 LeetCode 问题 #2

Question

以下是我的代码，它尝试将两个数字相加，这两个数字也以相反的顺序存储在链表中，returns 总和作为链表。

但是当我尝试在 LeetCode 中运行这段代码时，它指出这超过了时间。我假设它可能会卡在 while 循环中？

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution(object):
    def addTwoNumbers(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        result = ListNode()
        carry = 0 
    
        while l1 != None or l2 != None or carry:
            if l1 == None:
                v1 = 0
            else:
                v1 = l1.val
                
            if l2 == None:
                v2 = 0
            else:
                v2 = l2.val
        
            total = v1 + v2 + carry 
            carry = total // 10
            total = total % 10
        
            result.next = ListNode(total)
            
            if l1 != None:
                l1.next
                
            if l2 != None:
                l2.next
        
        return result

Answer 1

分析

这不过是一道简单的初等加法题。唯一的区别是要添加的数字由链表表示，其中每个数字由该链表的节点表示。

如果我们看到这个例子，那么我们会看到数字的顺序是相反的，即

First node => ones place
Second node => tens place
Third node => hundreds place
... and so on.

因此 2 -> 4 -> 3 实际上会生成 342，而 5 -> 6 -> 4 实际上会生成 465。

我们将不得不return一个新的链表，其节点将表示给定两个链表所表示的数字之和的数字。

方法

遍历两个链表。
在每次迭代中，添加链表节点中的数字。
如果列表不相等，则较小的列表会先于较长的列表结束。在这种情况下，我们将只放置剩余的节点结果列表中的列表更长。
如果两位数之和大于9，那么我们就得找出下一次迭代要加的“进位”。

这只不过是一个简单的加法。这里唯一的挑战可能是避免 NullPointerException 这在基于链表的问题中很常见。

时间复杂度

由于我们只迭代两个列表一次，时间复杂度为 O(m + n)。这里m和n是两个链表的节点数。

Space 复杂度

由于我们仅对变量使用额外的 space，因此 space 的复杂度为 O(1)。有人可能会争辩说我们正在使用另一个列表来存储我们的结果，因此 space 复杂度也应该是 O(m + n)。但这是我们没有用于算法的列表，我们将它用于问题中提出的结果（我很想知道你对此的看法）。

代码

def addTwoNumbers(l1: ListNode, l2: ListNode) -> ListNode:
    # Head of the new linked list - this is the head of the resultant list
    head = None
    # Reference of head which is null at this point
    temp = None
    # Carry
    carry = 0
    # Loop for the two lists
    while l1 is not None or l2 is not None:
        # At the start of each iteration, we should add carry from the last iteration
        sum_value = carry
        # Since the lengths of the lists may be unequal, we are checking if the
        # current node is null for one of the lists
        if l1 is not None:
            sum_value += l1.val
            l1 = l1.next
        if l2 is not None:
            sum_value += l2.val
            l2 = l2.next
        # At this point, we will add the total sum_value % 10 to the new node
        # in the resultant list
        node = ListNode(sum_value % 10)
        # Carry to be added in the next iteration
        carry = sum_value // 10
        # If this is the first node or head
        if temp is None:
            temp = head = node
        # for any other node
        else:
            temp.next = node
            temp = temp.next
    # After the last iteration, we will check if there is carry left
    # If it's left then we will create a new node and add it
    if carry > 0:
        temp.next = ListNode(carry)
    return head

Answer 2

在您编写的代码中，我只更改了很少的东西。

        result = ListNode(0)
        result_tail = result #### added 
        carry = 0 
    
        while l1 or l2 or carry:
            if l1 == None:
                v1 = 0
            else:
                v1 = l1.val
                
            if l2 == None:
                v2 = 0
            else:
                v2 = l2.val
        
            total = v1 + v2 + carry 
            carry = total // 10
            total = total % 10
        
            result_tail.next = ListNode(total)  ### edited
            result_tail = result_tail.next   ### added
            
            if l1 != None:
                l1 = l1.next ### edited
            else:
                l1 = None   ### added
                
            if l2 != None:
                l2 = l2.next    ### edited
            else:
                l2 = None    ### added
                
        return result.next   ### edited

我希望您知道的主要事情是，当您编写 l1.next 时，您只是给出了一个命令，该命令需要一个变量来存储值，因此更改会变为 l1 = l1.next。类似地，当您编写相同的语句时，您需要一个反 else 语句，您需要在 if 条件失败时解决该条件。由于该条件不存在，while 循环无限运行。

最后一部分是我添加了一个 result_tail。通过尝试和错误，我看到如果我们不添加它，那么结果的值会更新而不是被追加。

最后，这不是一个愚蠢的问题。只是一个友好的建议，如果你是超级新手，不要编写中级代码，而是从所有概念的简单代码开始。它将帮助您更多地了解 python 中的特定交易，例如字典、默认字典、列表理解、列表遍历、元组、集合、枚举器等。您可能之前做过竞争性编码，但老实说，新局总是从 0 开始。

使用 python 完成 LeetCode 问题 #2

using python to complete a LeetCode question #2

python

data-structures

python-3.x

分析

方法

时间复杂度

Space 复杂度

代码