Leetcode 筆記 :(2) Add Two Numbers[mediu]

tags: Leetcode

題目

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example

Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807

Example

Input: l1 = [0], l2 = [0]
Output: [0]

Example

Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
Output: [8,9,9,9,0,0,0,1]

解題思路

Linked-list

下面節錄至wiki

Singly linked list

Singly linked lists contain nodes which have a data field as well as 'next' field, which points to the next node in line of nodes. Operations that can be performed on singly linked lists include insertion, deletion and traversal.

簡單的說就是每個node裡面會包含兩個field， 一個是當前node的值，另外是指向下一個node的指標，最後一個節點則指向一個空值(null or None)。

LeetCode Solution

然後參考 leetCode 上面解答，如下圖

開始解答

class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        
        result = ListNode(0)
        node = result
        tmp = 0
        
        
        while l1  != None or l2 != None or tmp >0:
            if l1 is not None:
                tmp += l1.val
                l1 = l1.next
            if l2 is not None:
                tmp +=l2.val
                l2 = l2.next
                
            node.next = ListNode(tmp%10) # 取mod10
            node = node.next
            
            tmp = tmp//10
        return result.next

Reference

wiki
https://zh.wikipedia.org/wiki/链表

Linked List: Intro
https://medium.com/@havbgbg68/leetcode-2-add-to-numbers-python-63e4d5ba1534