002. Add Two Numbers

Question 2

https://leetcode.com/problems/add-two-numbers/description/

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 contain a single digit. Add the two numbers and return it as a linked list. You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

Answer

v1. 將所有的判斷式包在同一個 while 中

1. 紀錄一 ListNode 的開始（回傳用）

2. 宣告進位紀錄數字 -> carry

3. 宣告一 while 當 l1, l2, carry 都是 0 時才會停止迴圈

4. while 終須各自判斷 l1, l2 是否已經到底，避免無效的 .next 呼叫

5. 回傳時要回傳 Answer.next ，才不會將一開始宣告的 0 也回傳

v2. 分開處理 - 98.95%

1. 紀錄一 ListNode 的開始（回傳用）

2. 宣告進位紀錄數字 -> carry

3. 宣告一 while 當 l1 或 l2 沒有值時才便停止迴圈 裡面便不需要再判斷是否會呼叫到無效的 .next

4. 建立一 tmplist ，等於 l1 或 l2 尚有值的

5. 判斷 carry 是否不為零，將其加到 nodelist 中

v1

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

class Solution:
    def addTwoNumbers(self, l1, l2):
        
        # create a Answer node and mark it's start node
        StartAns = Answer = ListNode(0)
        carry = 0
        
        #keep counting until there's no next node
        while l1 or l2 or carry:
            
            v1 = v2 = 0
            # the end or not
            if l1 :
                v1 = l1.val
                l1 = l1.next
            if l2 :
                v2 = l2.val
                l2 = l2.next
            
            SumNum = v1 + v2 + carry
            carry, val = divmod(SumNum, 10)
            # create next node with SunNum
            Answer.next = ListNode( val )
            
            # to next node
            Answer = Answer.next
        
        #return without the first one node
        return StartAns.next

v2

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

class Solution:
    def addTwoNumbers(self, l1, l2):
        
        # create a Answer node and mark it's start node
        StartAns = Answer = ListNode(0)
        carry = 0
        
        # keep counting until one of nodes is end
        while l1 and l2:
            carry, sumval = divmod( l1.val+l2.val+carry, 10 )
            Answer.next = ListNode( sumval )
            
            # to next node
            l1 = l1.next
            l2 = l2.next
            Answer = Answer.next
            
        # if l1 or l2 still have next node
        tmplist = l1 or l2
        while tmplist:
            carry, sumval = divmod( tmplist.val+carry, 10 )
            Answer.next = ListNode( sumval )
            
            # to next node
            tmplist = tmplist.next
            Answer = Answer.next
            
        if carry != 0:
            Answer.next = ListNode(carry)
        
        #return without the first one node
        return StartAns.next