LeetCode 2. Add Two Numbers - C++

문제

---

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.

 

두 개의 양의 정수를 나타내는 비어 있지 않은 두 개의 연결 리스트가 제공된다.

숫자는 역순으로 저장되며, 각 노드에는 단일 숫자가 포함된다.

이 두 숫자를 더하고 합계를 연결 리스트로 반환한다.

두 숫자 모두 자신을 제외한 앞부분에 0을 포함하지 않는다고 가정한다.

 

 

예제

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]

 

제약

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.

 

문제 링크

LeetCode - The World's Leading Online Programming Learning Platform

 

 

풀이

---

연결리스트를 너무 오랜만에 봐서 예제로 준 코드를 보는게 더 오래걸렸다.

연결리스트 성질만 알면 금방 풀 수 있는 문제였다.

왜냐면 이 문제는 두 수의 덧셈을 하는 작업과 완벽하게 똑같기 때문이다.

 

아래와 같이 입력이 들어왔다고 해보자.

 

 

거꾸로 들어온다고 했고 출력도 거꾸로니, 들어온대로 더하는 과정을 진행해주면 된다.

가장 처음엔 2와 1이므로 더해서 새로운 노드에 3을 넣어준다.

값을 더할 때는 현재 노드가 널 포인터인지 확인을 해줘야한다. ▼

 

 

순조롭게 다음으로 넘어간다.

이번에는 5와 6을 더하는데, 각 노드는 0부터 9만 저장할 수 있으므로 뒷자리만 잘라서 넣어준다.

만약에 10을 넘어갔다면 이를 carry로 다음 값을 더할 때 넘겨준다. ▼

 

 

다음엔 6과 7이다.

허나 이전에 carry로 넘어온 값이 있으므로 둘이 더해서 14가 나오고, 뒷자리인 4가 노드에 들어간다.

역시나 이번에도 10이 넘었기 때문에 carry로 다음값에 전달된다. ▼

 

 

이번에는 두번째 리스트가 짧아 더할 값이 없다.

두번째 리스트는 현재 널 포인터로 전달이 됐을 것이고, 이는 널 체크를 통해 걸러졌을 것이다.

그렇기에 첫번째 리스트의 8과 캐리가 더해져 9로 노드에 저장된다. ▼

 

 

마지막으로 9가 더해지는데, 이번에는 캐리도 없으므로 그대로 저장된다. ▼

 

이런 과정을 통해 답을 구할 수 있다.

 

 

C++ 코드

---

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        int carry = 0;
        ListNode* head = new ListNode();
        ListNode* tail = head;

        while (l1 != NULL || l2 != NULL || carry) {
            int sum = 0;

            if (l1 != NULL) {
                sum += l1->val;
                l1 = l1->next;
            }
            if (l2 != NULL) {
                sum += l2->val;
                l2 = l2->next;
            }
            sum += carry;
            carry = sum / 10;

            ListNode* newNode = new ListNode(sum % 10);
            tail->next = newNode;
            tail = tail->next;
        }
        return head->next;
    }
};

 

while문의 조건으로 l1과 l2의 널 체크는 이해가 쉽게 되지만, carry는 왜 들어간거지? 라고 생각할 수 있다.

이는 99999 + 9999를 생각해보면 쉽다.

99999가 다섯자리긴 하지만 더하기 작업을 하고 나면 여섯자리가 된다. 이럴 때 carry값 체크를 하지 않으면 다섯자리에서 덧셈이 멈추게 되기에 carry값도 체크해야한다.