문제16: 두 수의 덧셈

아이디어는 얼추 알긴 알았는데, 구현실력이 너무 구리고, 사실 디테일적인 부분이 굉장히 약하다..

문제

입력

(2->4->3) + (5->6->4)

출력

7->0->8

풀이

1. O(n) 풀이: 나아가면서 두 연결리스트 노드의 값을 합으로 변경
1. 틀린 풀이….

l1_head = copy.copy(l1)
l2_head = copy.copy(l2)
l1_head.val = l2_head.val = (l1.val + l2.val) % 10

value = next = 0
while l1 != None and l2 != None:
    next, value = divmod(l1.val+l2.val+next, 10)
    l1.val = l2.val = value
    l1, l2 = l1.next, l2.next

if l1:
    while l1 != None:
        next, value = divmod(l1.val+next, 10)
        l1.val, l1 = value, l1.next
    if next:
        l1 = ListNode()
        l1.val = next
    return l1_head
elif l2:
    while l2 != None:
        next, value = divmod(l2.val+next, 10)
        l2.val, l2 = value, l2.next
    if next:
        l2 = ListNode()
        l2.val = next
    return l2_head	
else:
    if next:
        l1 = ListNode()
        l1.val = next
    return l1_head

1. 전가산기 구현

root = head = ListNode(0)

carry = 0
while l1 or l2 or carry:
	sum = 0
	if l1:
		sum += l1.val
		l1 = l1.next
	if l2:
		sum += l2.val
		l2 = l2.next
	
	carry, val = divmod(sum+carry, 10)
	head.next = ListNode(val)
	head = head.next

return root.next

새로운 개념

• root = head = ListNode(0)으로 초기화시, 처음값 저장해 두고 추적가능

• ListNode(val) 가능