[C++] LeetCode - Add Two Numbers (Linked List)

이번에는 linked list를 다루는 Add Two numbers 문제를 풀어봤습니다. linked list는 c++ 공부할 때 꼭 나오는 자료구조인데, 말그대로 포인터와 value로 이루어진 원소들이 서로 링크되어 있는 겁니다. next 를 통해서 링크를 타고 다음 원소로 넘어갈 수 있는데요.

---

깔끔한 풀이는 아니고, 속도 면에서 하위권에 속해있긴 하지만 어쨌든 풀게되었네요. 다른것보다 c++로 linked list를 다루려니, 문법적으로 잘 적응이 안되어 시간이 오래 걸렸네요. 만약 코딩 인터뷰에서 이렇게 헤맸으면 광탈날 뻔 했습니다.

---

문제 정의

---

---

접근 방법

• 두 개의 리스트가 nullptr가 아닐 때 차례대로 접근합니다.
• 두 수의 합이 10을 넘어가면, cnt 값에 1을 줘서, 다음 계산 시 더하게 합니다.
• 만약 끝에 남은 두 수의 합이 10이라면, 제시된 linked list의 길이보다 1만큼 길어야하므로, 별도로 추가해주는 코드가 있습니다.
• 하나의 while 문 안에 초기 값도 깔끔하게 들어가면 좋았을텐데, 생각보다 통합이 쉽지 않아서 초기 계산은 밖으로 빼놨습니다. 이것 때문에 분명히 런타임 손실이 많이 발생했겠네요.
• ** 제가 헷갈렸던 부분은, l1 = l1->next 이렇게 정의할 때, 만약 l1->next가 nullptr라면 오류가 날 것 같았는데, 다른 솔루션들을 보니 그렇게해도 괜찮고, 덕분에 while loop을 빠져나가는 것 같습니다. 이 부분만 바꾸면 초기 값도 while loop 안에 한번에 넣을 수 있겠네요.
• 시간 복잡도는 while loop 안에서 전체 원소를 다 더하는 과정이 있어서 아마도 O(n) 같은데... 조금 헷갈립니다.

---

코드

---

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
 
        int lastHandler = 0;
        ListNode* head = new ListNode(-1);
        ListNode* la = head;
        
        int t = l1->val + l2->val;
        int cnt=0;
        
        la->next = new ListNode(t % 10);
        if (t>=10) {
            cnt = 1;
            
        }
        la = la->next;
        if (l1->next == nullptr && l2->next == nullptr && cnt == 1) {
            la->next = new ListNode(1);
        }
        
        
        while(l1->next != nullptr || l2->next != nullptr) {
            
            int temp = 0;
            if (l1->next != nullptr) {
                temp += l1->next->val;
            }
            if (l2->next != nullptr) {
                temp += l2->next->val;
            }
            
            la->next = new ListNode((temp + cnt) % 10);
            
            la = la->next;
            if ((temp + cnt) >= 10) {
                cnt = 1;
            } else {
                cnt = 0;
            }
            if (l1->next != nullptr) {
                l1 = l1->next;
            }
            if (l2->next != nullptr) {
                l2 = l2->next;
            }
            if (l1->next == nullptr && l2->next == nullptr && cnt == 1) {
                la->next = new ListNode(1);
            }
        }
        
        
        
        
        
        return head->next;
    }
};

---