Add Two Numbers (Difficulty: Medium)
- 쉬운 문제라고 생각했는데 Linked List 예외처리가 의외로 경우의 수가 많았다. 주어진 l1과 l2의 길이가 다를 수 있다는 것이 포인트.
- l1 또는 l2가 하나만 값이 있는 경우
- 두개 모두 값이 없는 경우
- 두개 모두 값이 있는 경우
그리고 위에 더해서 밑 자리수에서 carry가 발생하는 경우까지 합하면 총 8가지의 경우의 수가 발생한다.
값이 없는 경우 l1.next를 참조하면 오류가 나니 if문으로 처리해주어야 한다.
아래 코드의 시간복잡도는 O(N)
l1과 l2의 길이의 차가 크다면 중간에 next를 긴 쪽으로 연결시켜 버리면 약간의 성능향상이 있을 듯하다. 하지만 Big-O는 최악의 경우를 상정하므로 변화는 없다.
# Definition for singly-linked list.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def get_val(self, node):
if node:
return node.val
else:
return 0
def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
base_node = ListNode()
prev_node = base_node
overflow = 0
while not(l1 == None and l2 == None and overflow == 0):
new_sum = self.get_val(l1) + self.get_val(l2) + overflow
overflow = new_sum // 10
new_sum -= overflow * 10
new_node = ListNode(new_sum)
prev_node.next = new_node
prev_node = new_node
l1 = l1.next if l1 else None
l2 = l2.next if l2 else None
return base_node.next