What is the best way to solve Add Two Numbers?

The optimized O(n) approach using Linked List patterns is generally preferred.

상위 150개 인터뷰쉬움

두 개의 숫자 추가

'두 숫자 더하기' 문제에 대한 자세한 가이드 및 Python 구현입니다.

문제 설명

쉬움

두 개의 음수가 아닌 정수를 나타내는 두 개의 비어 있지 않은 연결 목록이 제공됩니다. 숫자는 역순으로 저장되며 각 노드에는 단일 숫자가 포함됩니다. 두 숫자를 더하고 그 합계를 연결된 목록으로 반환합니다.

숫자 0 자체를 제외하고는 두 숫자에 선행 0이 포함되어 있지 않다고 가정할 수 있습니다.

연결된 목록은 Python 목록으로 표시됩니다. 합계를 역순의 목록으로 반환하는 함수 addTwoNumbers(l1: list, l2: list) -> list을 구현하세요.

제약

•The number of nodes in each linked list is in the range [1, 100]
•0 <= Node.val <= 9
•It is guaranteed that the list represents a number that does not have leading zeros

예

Example 1

Input

[2,4,3], [5,6,4]

Output

[7,0,8]

Explanation

342 + 465 = 807. Represented in reverse: [7,0,8].

Example 2

Input

[0], [0]

Output

[0]

Explanation

0 + 0 = 0.

Example 3

Input

[9,9,9,9,9,9,9], [9,9,9,9]

Output

[8,9,9,9,0,0,0,1]

Explanation

9999999 + 9999 = 10009998. Represented in reverse: [8,9,9,9,0,0,0,1].

Need a Hint?

세트나 힙과 같은 연결 목록 관련 데이터 구조를 사용하는 것을 고려해보세요.

Edge Cases to Watch

빈 입력 구조
단일 요소 입력
큰 수치 범위

해결할 준비가 되셨나요?

Open the problem in PyRun's browser-based Python editor. Your code runs fully offline — no server required.

편집기에서 열기

인터뷰 통찰력 및 변형

연결 목록 접근 방식의 논리를 설명하십시오.

null 또는 빈 입력과 같은 극단적인 경우에 대해 논의합니다.

복잡성 분석 분석

무차별 대입 복잡성

Time: O(n)•Space: O(1)

왜 시간인가?: Directly evaluates all possibilities.

왜 우주인가?: Uses standard local memory.

최적화된 복잡성

Time: O(n)•Space: O(1)

왜 시간인가?: Optimized paths reduce total operations.

왜 우주인가?: May trade memory for speed.

최적화된 솔루션 Python 코드

컴파일러에서 시도해 보세요

def add_two_numbers_opt(l1, l2):
    if isinstance(l1, list):
        node1 = build_linked_list(l1)
        node2 = build_linked_list(l2)
        res = add_two_numbers_opt_helper(node1, node2)
        return linked_list_to_list(res)
    return add_two_numbers_opt_helper(l1, l2)

def add_two_numbers_opt_helper(l1: ListNode, l2: ListNode) -> ListNode:
    dummy = ListNode(0)
    curr = dummy
    carry = 0
    while l1 or l2 or carry:
        val1 = l1.val if l1 else 0
        val2 = l2.val if l2 else 0
        total = val1 + val2 + carry
        carry = total // 10
        curr.next = ListNode(total % 10)
        curr = curr.next
        if l1: l1 = l1.next
        if l2: l2 = l2.next
    return dummy.next

무차별 대입 코드(스포일러 보호)

컴파일러에서 시도해 보세요

def add_two_numbers_brute(l1, l2):
    if isinstance(l1, list):
        node1 = build_linked_list(l1)
        node2 = build_linked_list(l2)
        res = add_two_numbers_brute_helper(node1, node2)
        return linked_list_to_list(res)
    return add_two_numbers_brute_helper(l1, l2)

def add_two_numbers_brute_helper(l1: ListNode, l2: ListNode) -> ListNode:
    def to_num(node):
        num, place = 0, 1
        while node:
            num += node.val * place
            place *= 10
            node = node.next
        return num
    total = to_num(l1) + to_num(l2)
    dummy = ListNode(0)
    curr = dummy
    for digit in str(total)[::-1]:
        curr.next = ListNode(int(digit))
        curr = curr.next
    return dummy.next or ListNode(0)