Leetcode 2. Add Two Numbers

Add Two Numbers : 此題給定兩個代表兩個非負整數的非空linked lists。這些數字以相反的順序儲存，並且它們的每個節點都包含一個數字。將兩個數字相加並將總和返回。

(ListNode想成List裡的每個小元素)

時間複雜度: O(n)

空間複雜度: O(1)

Python

class Solution(object):
    def addTwoNumbers(self, l1, l2):
        answer=ListNode(0)
        node=answer
        temp=0
        
        while l1 is not None or l2 is not None or temp>0:
            if l1 is not None:
                temp+=l1.val             // l1的值
                l1=l1.next               //下一位
            if l2 is not None:
                temp+=l2.val             //l2的值
                l2=l2.next               //下一位
            node.next=ListNode(temp%10)  //取出個位數
            node=node.next               //下一位
            temp=temp//10                //確認是否要進位
        return answer.next

class Solution(object):
    def addTwoNumbers(self, l1, l2):
        if not 11:
            return l2
        if not l2:
            return l1
        add=l1.val+l2.val
        temp=ListNode(add%10)                   //取餘數，加起來的個別值
        temp.next=self.addTwoNumbers(l1.next,l2.next)//遞歸，next下一位
        if add>=10:                         //大於10，需要進位，下一位+1
            temp.next=self.addTwoNumbers(temp.next,ListNode(1))
        return temp

C++

class Solution {
public:
  ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
    ListNode dummy(0);
    ListNode* tail = &dummy;
    int sum = 0;
    while (l1 || l2 || sum) {
      sum += (l1 ? l1->val : 0) + (l2 ? l2->val : 0);
      l1 = l1 ? l1->next : nullptr;  
      l2 = l2 ? l2->next : nullptr;
      tail->next = new ListNode(sum % 10);  #當大於10，取餘數加到下一位
      sum /= 10;            #sum 當前的值
      tail = tail->next;
    }            
    return dummy.next;   # head等於dummy.next
  }
};

時間複雜度: O(n)

空間複雜度: O(1)

Python

C++

相關