2. Add Two Numbers

Solution

새로운 링크리스트를 만들어서 합계 중 일의 자리만 저장하고 올림수를 따로 저장한다.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        temp = l1.val + l2.val
        ans = ListNode(temp%10)
        flag = int(temp/10)
        cur1 = l1.next
        cur2 = l2.next
        cur = ans

        while cur1 or cur2: # O(n)
            num1 = cur1.val if cur1 else 0
            num2 = cur2.val if cur2 else 0
            temp = num1 + num2 + flag
            flag = int(temp/10)
            cur.next = ListNode(temp%10)
            cur = cur.next
            if cur1: cur1 = cur1.next
            if cur2: cur2 = cur2.next
        
        if flag: cur.next = ListNode(1)

        return ans

C언어를 풀던 습관이 남아서

num1 = cur1.val if cur1 else 0
num2 = cur2.val if cur2 else 0

위의 코드도

if cur1: num1 = cur1.val
else: num1 = 0

if cur2: num2 = cur2.val
else: num2 = 0

이렇게 작성하고... 파이썬 문법이 너무 눈에 안 익는다. 그렇다고 이제는 씨언어도 모르겠고... 모든 걸 다 잃어버린 느낌. 🥵

시간 복잡도

링크 리스트를 돌아가면서 합계를 저장하는 방식이므로 두 개의 링크 리스트 중 더 긴 길이 만큼의 시간 복잡도를 가진다.

O(n)