2. Add Two Numbers

4306 ワード

Problem
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.
最初から問題を理解するのは難しい.文章をよく読んで、サンプルケースをよく見てください.
Trials
Case 1
class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode],
    l2: Optional[ListNode]) -> Optional[ListNode]:
        
        results = None
        
        l11, l22 = l1, 2
  
        while 1:
            if l11.next is None:
                break
                
            res = l11.val + l22.val
            if res > 9:
                res = int(str(res)[1])
            res_node = ListNode(res)
            
            if results is None:
                results = res_node
            else:
                results.next = res_node
            
            l11 = l11.next
            l22 = l22.next
            
            
        return results
Input [2,4,3], [5,6,4] , output [7,0]while loopは開始時にブレークポイントを掛けた.
Case 2
class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        
        results = None
        carry = 0
        
        while 1:
            if l1 is None or l2 is None:
                break
                
            val1, val2 = 0,0
            if l1 is not None:
                val1 = l1.val
                l1 = l1.next
            if l2 is not None:
                val2 =l2.val
                l2 = l2.next
            
            curr_sum = val1 + val2 + carry
            if curr_sum > 9:
                carry = 1
                curr_sum -= 10
            else:
                carry = 0
            
            if results is None:
                results = ListNode(curr_sum)
            else:
                results.next = ListNode(curr_sum)
                results = results.next
            
        return results
return付与は、積分を更新したresultsである.したがって、最後のノードの結果のみが出力されます.
Case 3
class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        
        results = ListNode()
        answer = results
        carry = 0
        
        while 1:
            if l1 is None and l2 is None:
                break
                
            val1, val2 = 0,0
            if l1 is not None:
                val1 = l1.val
                l1 = l1.next
            if l2 is not None:
                val2 =l2.val
                l2 = l2.next
            
            curr_sum = val1 + val2 + carry
            if curr_sum > 9:
                carry = 1
                curr_sum -= 10
            else:
                carry = 0
            
            
            results.next = ListNode(curr_sum)
            results = results.next

        return answer.next
最後の数字を加えると、carryが現れたら加算されます.しかし,現在のコードはリスト中のノード数のみを考慮し,加算により生成されたcarryを見失っている.
Final
class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        
        results = ListNode()
        answer = results
        carry = 0
        
        while 1:
            if l1 is None and l2 is None:
                break
                
            val1, val2 = 0,0
            if l1 is not None:
                val1 = l1.val
                l1 = l1.next
            if l2 is not None:
                val2 =l2.val
                l2 = l2.next
            
            curr_sum = val1 + val2 + carry
            if curr_sum > 9:
                carry = 1
                curr_sum -= 10
            else:
                carry = 0
            
            
            results.next = ListNode(curr_sum)
            results = results.next

        if carry:
            results.next = ListNode(1)
        return answer.next
Conlusion
  • LinkedListの最後のノードのnext()はnullである.
  • 結果は、
  • LinkedListの最後のノードを返します.
  • 加算については、Carryを常に考慮してください.