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 시작에 break문을 걸어놨다.

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

1. LinkedList의 마지막 노드의 next()는 null이다.
2. LinkedList의 마지막 노드를 결과로 리턴 했다.
3. 덧셈의 경우 Carry를 항상 고려하자.