문제

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.

Example 1:

Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807.

Example 2:

Input: l1 = [0], l2 = [0]
Output: [0]

Example 3:

Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
Output: [8,9,9,9,0,0,0,1]

Constraints:

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.

Python 풀이

# 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: ListNode, l2: ListNode) -> ListNode:
        resNode = tempNode = ListNode()
        carry = 0
        while l1 or l2 or carry:
            val_1 = val_2 = 0
            if l1 is not None:
                val_1 = l1.val
                l1 = l1.next
            if l2 is not None:
                val_2 = l2.val
                l2 = l2.next
            sum = val_1 + val_2 + carry
            carry = sum//10
            tempNode.next = ListNode(sum%10)
            tempNode = tempNode.next
        return resNode.next

문제 설명

• 문제의 그림과 같이 두개의 single linked list가 주어진다.
• 두 링크드 리스트의 꼬리 노드에서 헤드 노드순으로 하나의 숫자가 된다.
• <ex>
  1. 2(head node) -> 4 -> 3(tail node)
  2. 5(head node) -> 6 -> 4(tail node)
     1번 숫자는 342, 2번 숫자는 465가 된다.
• 두 숫자를 더해서 나온 결과 값을 한자리씩 다시 링크드 리스트로 만들어 준다. (역순으로)
  • 342 + 465 = 807
  • result : 7 -> 0 -> 8

코드 설명

• resNode = tempNode = ListNode()
  • resNode는 최종 결과를 저장할 Linked List
  • tempNode는 각 자리수를 더하면서 임시로 저장할 Linked List
• carry = 0
  • carry는 자리수끼리 더했을 때 10이 넘어가면 다음 자리수로 1을 올려주기 위한 변수
• while l1 or l2 or carry:
  • l1 또는 l2가 빈 값이 아니거나 (None이 아니거나, 즉, 값을 가지고 있거나) carry의 값이 1이면 반복문을 계속 실행한다.
  • 더하는 두 숫자의 자리수가 다를 수 있다. (문제에서 같다는 설명도 없고 Example3을 보면 서로 자리수가 다르다.) 따라서 둘 중 하나의 값이라도 갖고 있으면 자리수 덧셈을 계속 해줘야 한다.
    1. 둘 다 해당 노드가 값을 가지고 있으면 : 그냥 더하면 된다.
    2. 둘 중 하나만 값을 가지고 있으면 : 노드에 값이 없는 것은 값을 0으로 저장해주고 더하기를 진행한다.
    3. 둘 다 값이 없고 carry가 1이면 : 어쨋거나 carry가 1이므로 (다음 자리수에 1을 올려줘야 하므로) 더하기를 진행한다.
    4. 둘 다 노드에 값이 없고 carry도 0이면 : 더 이상 덧셈을 진행할 필요가 없다. 두자리수 + 두자리수 덧셈을 하는데 다섯번째 자리수가 뭐가 올지 계산하는 것과 똑같다. 굳이 할 필요가 없으니 반복문 종료
• val_1 = val_2 = 0
  • 두 리스트의 노드의 값을 0으로 초기화 해준다. 그 이유는 다음 줄에서 현재 이 리스트가 값을 가지고 있는지 확인할 건데 값이 없다면 0으로 더해줘야 하기 때문
    $12345 + 23$ 에서 두번째 자리까지 덧셈을 끝나고 세번째 자리수끼리 더하는 과정에서 $23$은 세번째 자리수가 없으므로 노드의 값이 없다.(None) 따라서 $12345 + 00023$ 이런 식으로 자리수가 더 많은 숫자와 자리수를 맞춰주기 위해 값을 0으로 저장해 준다는 뜻이다.

if l1 is not None:
    val_1 = l1.val
    l1 = l1.next
if l2 is not None:
    val_2 = l2.val
    l2 = l2.next

이 과정이 위에서 말한 것이다. 현재 이 노드가 값을 가지고 있으면 0으로 초기화 했던 val_1과 val_2값을 그 노드의 값으로 다시 저장한다. 그 다음 각 리스트를 다음 노드부터 시작하는 리스트로 바꿔준다.

• l1 = 2 -> 4 -> 3 이면 val_1 = 2가 되고 2를 따로 저장해 주었으니 l1 = 4 -> 3 으로 바꿔준다는 얘기이다.
• sum = val_1 + val_2 + carry
  • 자리수의 합을 저장한다. 첫째 자리수는 그 전에 더해서 올려주는 수가 없으므로 carry를 처음에 0으로 초기화해 주었으니 그냥 0이 더해진다. 그 다음 자리수 부터는 0이 올 수도 있고 1이 올 수도 있다.
• carry = sum//10
  • 더해준 값이 10을 넘어가면 sum//10을 해주면 몫이 1이 나온다. 10을 넘지 않으면 sum//10을 해주면 몫이 0이므로 carry비트는 0이다.
• tempNode.next = ListNode(sum%10)
  • tempNode를 처음에 tempNode = ListNode()로 해주었는데 코드 젤 위에 주석처리 된 곳을 보면 인자값에 self, val=0, next=None 이렇게 적혀있다. 인자가 들어올 곳에 이렇게 적어주면, 함수나 클래스를 호출할 때 인자값을 안넣어주면 내가 그냥 알아서 인자값 이걸로 설정할게~ 라고 컴파일러가 이해한다.
    그래서 인자값을 따로 안넣어 주었으므로 tempNode의 첫번째 값은 0이고 다음 연결된 노드는 없다는 뜻이다. (0 -> (None))
  • 아무튼 tempNode.next = ListNode(sum%10) 이라고 되어있으니 tempNode의 다음 노드에 sum%10의 값을 가진 노드를 연결한다는 뜻이다. sum = 7이었으니까 sum%10 = 7이고 tempNode의 다음 노드는 7이 된다. (0 -> 7 -> (None))
• tempNode = tempNode.next
  • 위에 if문에서 봤던 것처럼 현재 리스트를 다음 리스트로 바꿔준다는 뜻이다.
  • 현재 tempNode = 0 -> 7 -> (None) 이므로 tempNode.next = 7 -> (None)이고 tempNode = tempNode.next라고 하면 tempNode = 7 -> (None)이 된다.
• 이제 이걸 계속 반복하면 결과가 나온다.