LeetCode - 2. Add Two Number

[LeetCode] 2. Add Two Number

LeetCode 2번 문제를 풀어보았다.. Link

Problem

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

양수로 채워진 두개의 Linked list가 주어진다. 숫자들은 역순으로 저장되고, 각 노드에는 단일 숫자가 포함된다. 두 숫자의 합계를 Linked list으로 Return하라.

Intuition

어떤 특수한 알고리즘 사용이 필요하다기 보다는 Linked list Class의 특성을 이해하고 이를 코드로 옮기는 것이 중요하다고 생각했다.

Approach

1. 각 Linked list l1, l2의 각 노드의 단일 숫자들에 접근하여 숫자로 만든다.

   • Example) l1 = [2,4,3]이면 342로 만든다.

2. 두 숫자를 더한다음 String 타입으로 바꾸고 역순으로 변환한다.

3. 첫번째 노드를 만든다.

4. 반복문으로 다음 노드를 만들고 이전 노드의 next에 연결한다.

5. Linked list를 Return한다.

Complexity

• Time complexity:

  l1 과 l2의 길이를 각각 n, m이라고 하면, sum_l1을 구하는데 \(O(n)\), sum_l2를 구하는데 \(O(m)\), 그리고 새로운 Linked list를 만드는데 \(O(max(n, m)) or O(max(n, m)) +1\)으로, 정리하면 \(O(max(n, m))\) 이다.

• Space complexity: 새 Linked list의 길이는 최대 max(n, m) + 1로, \(O(max(n, m))\)이다

My Code

# 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]:
        """
        Input: two non-empty linked lists
        Output: the sum of the two numbers as a linked list
        Caution: The digits are stored in reverse order
        """
        sum_l1 = 0
        digit = 1
        while l1:
            sum_l1 += digit * l1.val
            l1 = l1.next
            digit *= 10

        sum_l2 = 0
        digit=1
        while l2:
            sum_l2 += digit * l2.val
            l2 = l2.next
            digit *= 10
        
        result = sum_l1 + sum_l2
        result = str(result)[::-1]
        print(result)
        base = ListNode(int(result[0]))
        t = base
        for i in range(1, len(result)):
            temp = ListNode(int(result[i]))
            while t.next:
                t = t.next
            t.next = temp
        
        return base

Others

내 풀이와 다르게 하나의 반복문에서 모든 처리를 하는 코드이다. l1과 l2의 길이 차이를 if .. else..문으로 해결하였다.

또한 특정 자리의 숫자를 계산함과 동시에 Single digit으로 치환 후 새로운 Node로 만들어 바로 Linked list에 붙인다.

class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        dummyHead = ListNode(0)
        curr = dummyHead
        carry = 0
        while l1 != None or l2 != None or carry != 0:
            l1Val = l1.val if l1 else 0
            l2Val = l2.val if l2 else 0
            columnSum = l1Val + l2Val + carry
            carry = columnSum // 10
            newNode = ListNode(columnSum % 10)
            curr.next = newNode
            curr = newNode
            l1 = l1.next if l1 else None
            l2 = l2.next if l2 else None
        return dummyHead.next