문제

l1, l2 총 두 개의 연결 리스트가 입력으로 주어진다.
우리가 해야 할 것은 각 각 노드들끼리 더해서 carry가 발생하는지 확인하고 carry가 발생할 시, carry까지 더해서 각 노드들을 더한 뒤, 결과 노드를 리턴해야 한다.

이 예시에서는 l1이 7개의 9, l2는 4개의 9로 이루어져있다.
l1의 첫 번째 노드 + l2의 첫 번째 노드 = 18 -> 캐리 발생!
이런식으로 쭉쭉 나가서 노드를 생성해나가면 되는 듯 하다.

풀이

• while 문을 사용해서 노드의 next가 null일 때 while을 종료해야 한다고 판단하였다.

• 만약 노드 간의 합이 10을 넘어가게 된다면, carry가 발생하기 때문에, 다음 노드 계산 시 carry + l1 + l2가 되게끔 설계해야 한다고 판단하였다.

• l1, l2의 길이가 서로 다를 때, 짧은 쪽은 계속해서 next를 생성해야 한다고 판단하였다.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptrptr) {}
 *     ListNode(int x) : val(x), next(nullptrptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {

        ListNode* head = new ListNode();
        ListNode* curr = head;

        int carry = 0;

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

            if(l1){
                sum += l1->val;
                l1 = l1->next;
            }

            if(l2){
                sum += l2->val;
                l2 = l2->next;
            }

            carry = sum / 10;

            curr->next = new ListNode(sum % 10);
            curr = curr->next;
        }

        if(carry){
            curr->next = new ListNode(carry);

        }
        
        return head->next;
        }
};

l1과 l2가 nullptr가 아닐 동안 while문을 수행한다.

sum과 carry 변수를 정의해놓았는데,

• sum : 두 노드 간 합
• carry : 두 노드 간 합에서 발생한 carry

여기서 carry가 발생하게 되면, 그 다음 노드 간 계산에서 sum에 carry를 포함해서 계산하게끔 한다.

그리고 l1과 l2가 nullptr 까지 도달했지만, 마지막 노드 간 덧셈에서 carry가 발생 할 경우, 마지막 노드를 생성하여 carry(1)의 값을 가지는 노드를 생성한다.

결과

https://leetcode.com/problems/add-two-numbers/submissions/1837692139

1ms가 떴었다.. ㅎㅎ
시간 복잡도는 O(n)으로 예상된다.