[LeetCode | Python] Add Two Numbers: 연결리스트 예제

✏️ 오늘 푼 문제

Add Two Numbers

✏️ 연관 개념

Linked List

✏️ 필요 사전지식

• 연결 리스트(Linked List): 각 요소가 노드로 구성되어있는 데이터구조. 각 노드는 데이터와 다음 노드를 가리키는 포인터로 이루어짐

• 자릿수 덧셈: 숫자를 더할 때 방법이 중요함. 올림(carry)을 고려하여 처리!

• 포인터 조작: 연결 리스트를 순회하면서 노드 이동 및 연결 필요

✏️접근 방법

1. 헤드 노드(첫 번째 값)에서 시작
2. 각 자리수를 더하고, 이전 연산에서의 올림을 더함
3. 새로운 연결 리스트에 결과값을 추가하고 만약 합이 10 이상(두자리수)이면 올림값(carry) 저장
4. 두 연결 리스트(l1, l2) 중 하나가 끝나면 남은 연결리스트와 올림값을 처리
5. 새 연결리스트 반환!

✏️ 코드

class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
    # 1. ListNode 객체(answer(리턴할 값), p(포인터)) 생성
    answer = ListNode()
    p = answer
    
    # 2. 올림수를 저장하는 변수
    carry = 0
    
    # 3. 계산 루프 시작
    while l1 or l2 or carry: # 처리해야 할 수가 남았을 때
    	sum = 0 # 각 자리수의 합
        if l1:
        	sum += l1.val # l1의 현재 자리수
            l1 = l1.next # l1의 다음 자리수
        if l2:
        	sum += l2.val
            l2 = l2.next
        sum += carry
        carrry = sum // 10 # 올림수는 한자리수니까 10으로 나눠주기!
        sum %= 10 # 올림수 제거하고 현재 자리수만 계산
        
        p.next = ListNode(sum) # 결과저장하는 연결리스트 생성
        p = p.next
        
    return answer.next
        

끝