Intuition

더하기를 진행할 때 일의 자리부터 진행하게 되는데, 문제에서도 역순으로 된 linked list를 input으로 주고 있기 때문에 주어진 linked list를 순서대로 순회하며 더하면 될 것이라 생각했다. 이때, carry와 남는 자리수들에 대해서 신경쓰면서 풀이했다.

Approach

결과값을 담을 Node를 매번 새로 생성해야 하기 때문에 새로운 노드를 생성하는 함수를 선언했다.

struct ListNode* newNode(int num){
    struct ListNode* node=(struct ListNode*)malloc(sizeof(struct ListNode));
    node->val=num;
    node->next=NULL;
    return node;
}

이후 결과값을 return 해주기 위한 head와 그때그때 새로 생성되는 node를 처리할 cur을 선언했다. carry는 0, head는 NULL로 초기화시켰다.

    struct ListNode *head, *cur;
    int carry=0;
    head=NULL;

이제 두 숫자가 모두 끝날때까지 연결 리스트를 순회한다. 서로 자릿수가 달라, 어느 한쪽이 NULL이 되었을 때도 나머지 한쪽이 끝날때까지 순회할 수 있도록 하기 위해서, sum을 구하는 단계와 다음 연결리스트로 넘어가는 과정에서 각각 NULL여부를 판단한 후 진행했다. 새로운 노드의 val값은 나머지 연산을 통해 자연스럽게 carry와 분리시켰다. 마찬가지로 carry도 나누기 연산을 통해 그 값을 구했다.

    while(l1||l2){
        int sum=(l1?l1->val:0)+(l2?l2->val:0)+carry; // NULL 여부 판단

        if(!head) head=cur=newNode(sum%10); // 나머지 연산이 아니라 minus 연산을 하게 되면 10을 기준으로 나눠서 진행해야하는 번거로움이 있다.
        else{
            cur->next=newNode(sum%10);
            cur=cur->next;
        }

        carry=sum/10;

        if (l1) l1=l1->next; // NULL 여부 판단
        if (l2) l2=l2->next;
    }

마지막으로 carry가 1이라면 새로운 노드를 생성하여 자리수를 추가해줬다.

    if (carry) cur->next=newNode(1);

Solution

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

struct ListNode* newNode(int num){
    struct ListNode* node=(struct ListNode*)malloc(sizeof(struct ListNode));
    node->val=num;
    node->next=NULL;
    return node;
}

struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2){
    struct ListNode *head, *cur;
    int carry=0;
    head=NULL;

    while(l1||l2){
        int sum=(l1?l1->val:0)+(l2?l2->val:0)+carry;

        if(!head) head=cur=newNode(sum%10);
        else{
            cur->next=newNode(sum%10);
            cur=cur->next;
        }

        carry=sum/10;

        if (l1) l1=l1->next;
        if (l2) l2=l2->next;
    }

    if (carry) cur->next=newNode(1);

    return head;
}

Complexity

Time Complexity

$l1$과 $l2$중 더 긴쪽의 길이만큼 진행된다. $O(n)$

Space Complexity

$l1$과 $l2$중 더 긴쪽의 길이보다 최대 +1만큼 필요하다 $O(n)$

지적 및 질문 환영