LeetCode

LeetCode 2 Add Two Numbers 풀이: 연결 리스트로 세로 덧셈 구현

2026년 10월 13일

작성·코드 검증: solve together · 작성 언어: Python

0. 문제 링크와 출처

문제: 2. Add Two Numbers
출처: LeetCode
학습: 연결 리스트 학습 가이드
자체 판단 난이도: Level 3

두 숫자의 자릿수가 역순으로 연결 리스트에 저장되어 있어, 노드 순회와 세로 덧셈의 자리 순서를 맞춰야 한다. 여기에 리스트 길이 차이와 마지막 올림을 놓치지 않고 결과 노드로 연결해야 하므로 Level 3으로 판단했다.

문제 원문과 제한 조건은 바뀔 수 있으므로 제출 전에 공식 문제 페이지를 다시 확인한다.

1. 문제 요약

음이 아닌 정수 두 개가 각각 단일 연결 리스트로 주어진다. 각 노드에는 한 자리 숫자가 들어 있고, 숫자는 일의 자리부터 역순으로 저장되어 있다. 두 수의 합도 같은 역순 연결 리스트로 만들어 반환한다.

중요한 조건은 다음과 같다.

두 리스트는 비어 있지 않고, 각 리스트의 노드 수는 1 이상 100 이하이다.
각 노드 값은 0부터 9까지다.
숫자의 앞에 불필요한 0은 없으며, 숫자 0 자체는 [0]으로 표현된다.
두 리스트의 길이는 서로 다를 수 있다.

예제의 [2, 4, 3]은 342이고 [5, 6, 4]는 465다. 합 807을 일의 자리부터 적으면 결과는 [7, 0, 8]이다.

2. 문제 해결에 사용되는 알고리즘이나 자료구조 설명

역순 저장이 덧셈 순회와 맞아떨어진다

세로 덧셈은 일의 자리에서 시작해 왼쪽으로 진행하고, 각 자리에서 생긴 올림을 다음 자리에 더한다. 이 문제의 연결 리스트도 일의 자리부터 저장하므로 두 head에서 시작해 next로 이동하는 순서가 바로 세로 덧셈 순서다. 숫자를 먼저 뒤집거나 정수로 변환할 필요 없이 두 리스트를 한 번씩 순회하면 된다.

각 단계에서 유지하는 상태는 두 입력 노드, 결과 리스트의 끝 노드 tail, 그리고 다음 자리에 더할 carry다. 리스트 하나가 끝났을 때 그 자리의 숫자는 0으로 취급한다.

자리별 합과 올림의 불변식

매 반복에서 현재 숫자 둘과 이전 자리의 올림을 더한다.

total = digit1 + digit2 + carry
현재 결과 숫자 = total % 10
다음 carry = total // 10

입력 숫자는 각각 한 자리이므로 total은 최대 9 + 9 + 1 = 19, 따라서 carry는 항상 0 또는 1이다. 매 반복이 끝났을 때 결과 리스트에는 지금까지 계산한 낮은 자리들이 순서대로 저장되고, carry는 아직 처리하지 않은 바로 다음 자리에 더해야 할 값이다.

공식 예제의 자릿수별 상태는 다음과 같다.

자리	계산	결과 노드	다음 `carry`
일의 자리	`2 + 5 + 0 = 7`	7	0
십의 자리	`4 + 6 + 0 = 10`	0	1
백의 자리	`3 + 4 + 1 = 8`	8	0

따라서 결과 연결 리스트는 7 -> 0 -> 8, 즉 역순 표현 [7, 0, 8]이다.

길이 차이와 마지막 올림을 같은 반복으로 처리하기

반복 조건은 l1, l2, carry 중 하나라도 남아 있는 동안이다.

한 리스트가 먼저 끝나면 그 자리의 값은 0으로 계산하고 긴 리스트를 계속 처리한다.
두 리스트가 모두 끝났더라도 carry가 남아 있으면 올림을 저장할 새 노드를 만든다.

예를 들어 [9] + [1]은 첫 자리에서 10이 되어 결과 노드 0과 올림 1을 만든다. 입력 노드는 모두 소진되었지만 올림이 남아 있으므로 한 번 더 반복해 [0, 1]을 완성한다. 이 조건 덕분에 마지막 올림을 별도의 후처리 분기로 처리할 필요가 없다.

결과의 첫 노드를 매번 별도로 처리하지 않도록 dummy 노드를 사용한다. 새 숫자 노드를 tail.next에 붙이고 tail을 이동한 뒤 dummy.next를 반환한다. 입력 리스트를 변경하지 않고 결과 노드를 새로 만든다.

오답 접근과 반례

연결 리스트를 평소 숫자 표기처럼 왼쪽부터 읽으면 자리값을 거꾸로 해석한다. [1, 2]는 12가 아니라 21이고 [3]은 3이다. 따라서 정답은 24를 역순으로 쓴 [4, 2]다. 앞에서부터 12 + 3으로 계산하면 잘못된 결과 [5, 1]을 얻게 된다.

또한 반복 조건에서 carry를 빼면 마지막 자리를 잃는다.

[9] + [1]
첫 자리: 9 + 1 = 10 -> 결과 자리 0, carry 1
잘못된 종료 결과: [0]
올바른 결과: [0, 1]

재귀 풀이와 비교

재귀 함수에 두 노드와 carry를 전달해 같은 자리 계산을 한 뒤, 다음 노드 결과를 재귀 호출로 연결할 수도 있다. 이 방식은 자리별 흐름이 함수 호출에 드러나지만, 노드 수에 비례하는 호출 스택을 사용한다. 여기서는 입력 노드 수가 최대 100이고 반복문으로 동일한 계산을 표현할 수 있으므로, 호출 스택을 추가하지 않는 반복형 풀이를 선택한다.

시간·공간 복잡도

리스트 길이를 각각 m, n이라 하면 가장 긴 리스트와 마지막 올림을 한 번씩 처리하므로 시간 복잡도는 O(max(m, n))이다. 결과 리스트는 최대 max(m, n) + 1개의 노드를 사용한다. 결과를 제외한 추가 공간은 포인터와 carry뿐이므로 O(1)이다.

3. 문제 해결 코드 (Python)

각 반복에서 존재하는 노드의 숫자만 total에 더하고, 노드가 없는 쪽은 자연스럽게 0으로 둔다. divmod(total, 10)은 다음 자리의 올림과 현재 결과 자리를 함께 계산한다.

class Solution:
    def addTwoNumbers(
        self,
        l1: 'ListNode | None',
        l2: 'ListNode | None',
    ) -> 'ListNode | None':
        dummy = ListNode(0)
        tail = dummy
        carry = 0

        while l1 is not None or l2 is not None or carry:
            total = carry

            if l1 is not None:
                total += l1.val
                l1 = l1.next

            if l2 is not None:
                total += l2.val
                l2 = l2.next

            carry, digit = divmod(total, 10)
            tail.next = ListNode(digit)
            tail = tail.next

        return dummy.next

dummy는 결과 시작 노드를 일정한 방식으로 붙이기 위한 임시 노드다. 반환할 때는 실제 첫 결과 노드인 dummy.next를 반환한다. 새 노드를 생성하므로 입력 리스트의 링크는 바뀌지 않는다.

복사해 실행할 테스트

LeetCode 실행 환경에는 ListNode가 제공된다. 로컬에서 실행하려면 아래 최소 ListNode 정의를 풀이 클래스보다 앞에 두고, 빌더·비교 헬퍼와 assert를 클래스 뒤에 붙인다.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


def make_list(values):
    dummy = tail = ListNode()
    for value in values:
        tail.next = ListNode(value)
        tail = tail.next
    return dummy.next


def to_list(node):
    values = []
    while node is not None:
        values.append(node.val)
        node = node.next
    return values


assert to_list(Solution().addTwoNumbers(make_list([2, 4, 3]), make_list([5, 6, 4]))) == [7, 0, 8]
assert to_list(Solution().addTwoNumbers(make_list([0]), make_list([0]))) == [0]
assert to_list(Solution().addTwoNumbers(make_list([9, 9, 9, 9, 9, 9, 9]), make_list([9, 9, 9, 9]))) == [8, 9, 9, 9, 0, 0, 0, 1]
assert to_list(Solution().addTwoNumbers(make_list([9]), make_list([1]))) == [0, 1]
assert to_list(Solution().addTwoNumbers(make_list([1, 2]), make_list([3]))) == [4, 2]

4. 공식 예제와 추가 검증

위 assert를 연결 리스트 노드로 직접 구성해 실행했다. 공식 예제 세 가지와 짧은 쪽 리스트가 먼저 끝나는 경우, 마지막 올림만 남는 경우를 확인했다.

공식 예제 1

입력: l1 = [2, 4, 3], l2 = [5, 6, 4]
기대 출력: [7, 0, 8]
실행 결과: 통과
검증 목적: 여러 자리의 일반적인 덧셈과 중간 올림 확인

공식 예제 2

입력: l1 = [0], l2 = [0]
기대 출력: [0]
실행 결과: 통과
검증 목적: 0을 나타내는 최소 입력 확인

공식 예제 3

입력: l1 = [9, 9, 9, 9, 9, 9, 9], l2 = [9, 9, 9, 9]
기대 출력: [8, 9, 9, 9, 0, 0, 0, 1]
실행 결과: 통과
검증 목적: 길이가 다른 입력에서 연속 올림이 전파되는지 확인

추가 검증: 마지막 올림이 새 노드를 만드는 경우

입력: l1 = [9], l2 = [1]
기대 출력: [0, 1]
실행 결과: 통과
검증 목적: 두 입력 노드가 끝난 뒤 남은 올림을 결과에 추가하는지 확인

추가 검증: 첫 리스트가 더 긴 경우

입력: l1 = [1, 2], l2 = [3]
기대 출력: [4, 2]
실행 결과: 통과
검증 목적: 짧은 리스트가 끝난 뒤 남은 자리를 0과 더해 처리하는지 확인

5. 다른 풀이 방식 검색 및 비교

Add Two Numbers 공식 문제는 역순 숫자 연결 리스트 두 개의 합을 같은 형식으로 반환하도록 정의한다.
NeetCode의 Add Two Numbers 설명은 반복형과 재귀형으로 자릿수별 합과 올림을 계산하는 방법을 함께 소개한다.

재귀형은 다음 자리 계산을 재귀 호출에 맡겨 풀이 흐름을 짧게 표현할 수 있다. 다만 노드 수만큼 호출 스택이 필요하므로 추가 공간이 O(max(m, n))이다. 이 글의 반복형은 동일한 자리 계산을 수행하면서 결과를 즉시 연결하고, 결과 노드를 제외한 추가 공간을 O(1)로 유지한다.

마무리

역순 연결 리스트의 head는 일의 자리이므로, 두 리스트를 동시에 따라가며 세로 덧셈을 그대로 구현할 수 있다. 매 자리에서 digit1 + digit2 + carry를 계산하고 결과 자릿수와 다음 올림을 분리한다. 반복 조건에 마지막 carry까지 포함하면 길이 차이와 결과의 새 최고 자리를 한 번의 반복문으로 모두 처리할 수 있다.