[C] LeetCode 2. Add Two Numbers

문제(원문)

 

문제(번역)

비어있지 않으면서 음수가 아닌 두 linked list가 주어진다. 이 수들은 역순으로 정렬되어 있고, 각 노드는 하나의 숫자만 갖고 있다.

이둘을 더한 linked list를 반환해라.

단, 이 linked list에는 0인 경우를 제외하고 앞에 0이 들어있지 않다.

 

접근 방법

그냥 Linked List를 순회하면서 수를 더하되, 10을 넘어가면 그 수를 다음에 보내서 더해주는 로직만 잘 작성하면 된다.

하지만 Linked List를 할당하는 것과 Null 처리하는 부분을 조심하지 않으면 쉽게 에러가 난다.

 

소스 코드

int safeGet(struct ListNode* l) {
    if(l == NULL) return 0;
    return l->val;
}

struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
    struct ListNode *ptr1=l1, *ptr2=l2, *bef=NULL;
    short acc = 0;
    while(ptr1 || ptr2 || acc) {
        if(ptr1 == NULL) {
            ptr1 = (struct ListNode*)malloc(sizeof(struct ListNode));
            ptr1->val = 0;
            ptr1->next = NULL;
            bef->next = ptr1;
        }
        short sum = safeGet(ptr1) + safeGet(ptr2) + acc;
        acc = sum / 10; ptr1->val = sum % 10;
        bef = ptr1;
        ptr1 = ptr1->next;
        ptr2 = (ptr2) ? ptr2->next : NULL;
    }
    return l1;
}

실행속도의 경우 한번씩만 순회하니 빠르고, 메모리의 경우 약간 아쉬웠다.