문제

1의자리부터 한 자리씩 링크드리스트에 저장되어있는 2수를 합한 것을 링크드 리스트에 더해서 반환하라.
ex) 123 + 456 = 579
3-2-1

• 6-5-4
  =>9-7-5 정답

해결과정

필요 변수

1. Carry (1 or 0) => 더 했을때 10이 넘어가는 경우 올림 저장
2. answer => 답을 저장하고있는 링크드리스트의 첫 노드 저장
3. cur => 현재 자리를 더한 값을 저장하는 노드
4. first, second => 각 링크드 리스트의 현재 노드

생각

1. 3개의 노드를 가리키는 포인터가 각자 링크드 리스트를 이동
2. Carry가 있는 경우 1을 다음에 더하고 현재는 10의 나머지를 저장
3. 루프 탈출 조건은 첫번째 링크드 리스트와 두번째 링크드 리스트 노드의 next가 없고 Carry가 0일때

복잡도

첫번째 링크드 리스트 N
두번째 링크드 리스트 M

시간복잡도

Worst N+1
O(Max(N,M))

공간복잡도

Worst N + M + Max(N,M) + 1
O(Max(N,M))

코드

# 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]:
        first = l1
        second = l2
        carry = 0
        answer = ListNode()
        cur = answer
        val1 = first.val
        val2 = second.val
        while True:
            summation = val1 + val2 + carry
            if summation >= 10:
                carry = 1
                summation = summation % 10
            else:
                carry = 0
           
            
            #make new node to store the summation
            cur.val = summation
            
            #escape condition
            if first.next == None and second.next == None and carry == 0:
                break
                
            if first.next != None:
                first = first.next
                val1 = first.val
            else:
                val1 = 0
            if second.next != None:
                second = second.next
                val2 = second.val
            else:
                val2 = 0
                
            #change cur to next node
            cur.next = ListNode()
            cur = cur.next
        #while end
        
        return answer

잘못된 내용에 대한 피드백 환영 합니다