时间戳

首页 > 解决方案 > 使用 python 完成 LeetCode 问题 #2

python - 使用 python 完成 LeetCode 问题 #2

问题描述

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

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

提前谢谢你的帮助。我对 Python 非常陌生，很抱歉这个愚蠢的问题。 

# 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

标签： pythonpython-3.xdata-structures

解决方案

分析

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

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

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

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

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

方法

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

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

时间复杂度

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

空间复杂度

因为我们只为变量使用额外的空间，所以我们的空间复杂度是 O(1)。有人可能会争辩说我们正在使用另一个列表来存储我们的结果，因此空间复杂度也应该是 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

我希望它能解决你的问题。

Sran012

推荐阅读