Add Two Numbers

문제

두 개의 비어 있지 않은 연결 리스트가 주어집니다. 이 연결 리스트들은 각각 음이 아닌 정수를 나타냅니다. 각 숫자는 역순으로 저장되며, 각 노드는 단 하나의 숫자만 포함합니다. 이 두 숫자를 더하고 그 합계를 연결 리스트로 반환하세요. 두 숫자가 0이 아니라면 앞에 0이 오지 않는다고 가정해도 됩니다.

접근 방향

파라미터로 입력받는 두 노드를 순회하면서 노드의 값들을 미리 선언한 배열에 순서대로 삽입한 뒤 이 배열을 뒤집어 두 배열의 합을 계산한 다음, 다시 이 배열을 뒤집어 반복문으로 순회하며 이 배열 안에 있는 값들로 새로운 리스트 노드를 생성해나갑니다.

나의 풀이

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

class Solution(object):
  def addTwoNumbers(self, l1, l2):
    """
    :type l1: ListNode
    :type l2: ListNode
    :rtype: ListNode
    """
    # 리스트 노드의 값을 담을 배열을 생성합니다.
    bucket1 = []
    bukect2 = []

    # l1을 순회하면서 배열 안에 노드의 값을 삽입
    while l1:
      bucket1.append(l1.val)
      l1 = l1.next

    # l2를 순회하면서 배열 안에 노드의 값을 삽입
    while l2:
      bucket2.append(l2.val)
      l2 = l2.next

    # 두 노드의 값을 덧셈하기 위해 숫자로 변환
    num1 = int(''.join(map(str, bucket1[::-1])))
    num2 = int(''.join(map(str, bucket2[::-1])))

    # 두 노드의 값을 덧셈
    res = num1 + num2

    # 덧셈한 숫자를 다시 하나씩 쪼개 배열로 변환 후 뒤집기
    res = [int(i) for i in str(res)]
    res = res[::-1]

    # 신규 노드 생성 후 노드를 cur 변수에 담기
    node = ListNode(res[0])
    cur = node

    # 생성한 노드의 다음 노드 생성
    for i in range(1, len(res)):
      cur.next = ListNode(res[i])
      cur = cur.next

    # 생성한 노드 반환 (head)
    # 여기서는 node가 첫 번째 노드(head)를 가리키고 cur이 마지막 노드(tail)를 가리키게 된다.
    return node

다른 사람의 풀이

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

class Solution(object):
    def addTwoNumbers(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        # 더미 노드 생성 (dummy.next is head)
        dummy = ListNode(0)

        # 더미 노드를 curr에 담기 (tail)
        curr = dummy
        carry = 0

        # 두 연결 노드를 모두 순회
        while l1 or l2:
            sum_val = carry

            # 노드가 존재한다면 각 노드의 값을 sum_val에 추가 후 다음 노드 이동
            if l1:
                sum_val += l1.val
                l1 = l1.next
            if l2:
                sum_val += l2.val
                l2 = l2.next

            # 두 노드의 값을 더한 결과, 10보다 같거나 클 경우 몫을 담기 (다음 노드에 덧셈)
            carry = sum_val // 10
            # 나머지 값을 현재 생성할 노드에 값으로 저장
            curr.next = ListNode(sum_val % 10)
            # 다음 노드 지정
            curr = curr.next

        # carry 값이 존재할 경우 curr 노드 기준 다다음 노드에 carry를 노드의 값으로 생성
        if carry:
            curr.next = ListNode(carry)

        return dummy.next

나의 풀이는 노드의 값을 통째로 더하였지만 위 코드는 우리가 일반적으로 덧셈을 하는 방식처럼 10보다 같거나 클 경우 그 증감값을 다음 계산에 미리 노드를 생성하여 반영하도록 한 모습이다.