C언어 ] leetCode 2 - Add Two Numbers

 

 

 

 

leetCode 2 문제

 

 

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.

 

 

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] 

 

Constraints: 

• 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.

 

 

문제를 보고 처음엔 l1와 l2가 나타내는 숫자를 확인하여 더한 뒤 그 숫자를 나타내는 링크드 리스트를 만들면 되지않나 생각할 수 있지만 그렇게는 불가능하다.

 

링크드 리스트의 노드 개수가 1개에서 100개 사이로 주어지는데 10의 99승(캐리발생한 경우엔 100승)에 해당하는 수를 담을 수 있는 정수형 변수가 없기 때문이다.

 

따라서 두 링크드 리스트의 첫번째 노드부터 순회하며 더한값을 새 링크드리스트에 삽입하는 방법을 택해야한다. 일반적인 링크드 리스트 API는 아니지만 문제를 풀기위해 appendNode라는 함수를 만들어 풀었다.

 

설명은 주석으로 대신한다.

 

 

struct ListNode *appendNode(struct ListNode* tail, int data) {
    
    // 새로운 노드를 생성한다.
    struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));
    if(newNode == NULL) return NULL;
    
    // 새 노드를 초기화한다.
    newNode->val = data;
    newNode->next = NULL;
    
    // 리스트가 비어있으면 새 노드를 tail로하고, 비어있지 않은 경우 tail 뒤에 새 노드를 추가한다.
    if(tail == NULL) {
        tail = newNode;
    }
    else {
        tail->next = newNode;
        tail = newNode;
    }
    
    return tail;
}

struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {

	// 새 리스트의 head와 tail을 가리킬 노드 포인터를 만들고 초기화한다.
    struct ListNode* head = NULL;
    struct ListNode* tail = NULL;
    
    // carry를 저장할 변수를 0으로 초기화한다.
    int carry = 0;
    
    while(l1 != NULL || l2 != NULL) {
        
        // l1과 l2 두 리스트의 값과, 그리고 직전에 발생한 carry를 더해 temp 변수에 저장한다.
        int temp = 0;
        if(l1 != NULL) temp += l1->val;
        if(l2 != NULL) temp += l2->val;
        temp += carry;
        
        // temp의 1의 자리 숫자를 새 리스트에 추가하고, 빈 리스트인 경우 head가 가리키게 한다.
        tail = appendNode(tail, temp % 10);
        if(head == NULL) head = tail;
        
        // temp의 10의 자리 숫자를 carry에 저장한다.
        carry = temp / 10;
        
        // l1과 l2가 NULL이 아닌경우 다음 노드로 이동한다.
        if(l1 != NULL) l1 = l1->next;
        if(l2 != NULL) l2 = l2->next;
    }
    
    // 마지막 carry가 있는 경우 새 리스트에 추가한다.
    if(carry != 0) tail = appendNode(tail, carry);
    
    return head;
}

 

 

 

 

 

아래는 OnlineGDB에서 테스트로 돌려본 것

 

#include <stdio.h>
#include <stdlib.h>

struct ListNode {
    int val;
    struct ListNode* next;
};

struct ListNode *appendNode(struct ListNode* tail, int data) {
    
    struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));
    if(newNode == NULL) return NULL;
    
    newNode->val = data;
    newNode->next = NULL;
    
    if(tail == NULL) {
        tail = newNode;
    }
    else {
        tail->next = newNode;
        tail = newNode;
    }
    
    return tail;
}

struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
    
    struct ListNode* head = NULL;
    struct ListNode* tail = NULL;

    int carry = 0;
    
    while(l1 != NULL || l2 != NULL) {
        int temp = 0;
        if(l1 != NULL) temp += l1->val;
        if(l2 != NULL) temp += l2->val;
        temp += carry;
        tail = appendNode(tail, temp % 10);
        if(head == NULL) head = tail;
        carry = temp / 10;
        if(l1 != NULL) l1 = l1->next;
        if(l2 != NULL) l2 = l2->next;
    }

    if(carry != 0) tail = appendNode(tail, carry);
    
    return head;
}

void printNode(struct ListNode *head) {
    while(head != NULL) {
        printf("%d ", head->val);
        head = head->next;
    }
    printf("\n");
}

void freeNode(struct ListNode *head) {
    while(head != NULL) {
        struct ListNode* temp = head->next;
        free(head);
        head = temp;
    }
    
}

int main()
{
    struct ListNode *l1;
    struct ListNode *l1_tail;
    struct ListNode *l2;
    struct ListNode *l2_tail;
    struct ListNode *result;
    
    l1 = l1_tail = appendNode(l1_tail, 2);
    l1_tail = appendNode(l1_tail, 4);
    l1_tail = appendNode(l1_tail, 3);
    
    l2 = l2_tail = appendNode(l2_tail, 5);
    l2_tail = appendNode(l2_tail, 6);
    l2_tail = appendNode(l2_tail, 4);
    
    printNode(l1);
    printNode(l2);
    
    result = addTwoNumbers(l1, l2);
    
    printNode(result);
    
    freeNode(l1);
    freeNode(l2);
    freeNode(result);

    return 0;
}