# 【LeetCode】2. Add Two Numbers

## Question link
[Link](https://leetcode.com/problems/add-two-numbers/description/)

## Intuition
>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.
> 題目表明給定是兩個 **non-empty** 的`ListNode`，表示的數字以 **reverse-order** 儲存，這意味著低位數字放在`ListNode` 的開頭，我們需要將兩個數字相加並以相同的方式返回`ListNode`

## Approach

1. 初始化一個`result`作為返回的結果，同時設置指標`p`指向這個鏈結
2. 初始化`num`以及`carry`，用於處理相加之後的結果與進位值，初始化為零
3. 接著需要遍歷兩個輸入鏈結與處理進位，直到兩個鏈結都處理完且所有進位也都處理完畢，所以條件為`while(l1 || l2 || carry)`
* 將`carry`賦值到`num`，用於處理有進位的數值
* 逐位將`l1`與`l2`值取出相加，如果有`l1`或`l2`的話，並且更新
* 將`carry`更新成當前的數值
* 將`num % 10`存入當前節點
4. 如果今天`l1`與`l2`都歷遍完成，需要檢查最後是否需要進位，但由於前面迴圈判斷式已經處理這個條件了所以這邊不要再判斷
5. 返回`result->next`，跳過初始化的頭節點(又稱哨兵節點sentinel node或者dummy head)

## Complexity
- Time complexity: $O(max(n_1, n_2))$
- Space complexity: $O(max(n_1, n_2))$
## Code

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
    struct ListNode* result = malloc(sizeof(struct ListNode));
    struct ListNode* p = result;
    result->val = 0;
    result->next = NULL;
    int carry = 0, num = 0;
    while (l1 || l2 || carry){
        num = carry;
        if (l1) {
            num += l1->val;
            l1 = l1->next;
        }

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

        carry = num / 10;
        num = num % 10;

        struct ListNode* new = malloc(sizeof(struct ListNode));
        new->val = num;
        new->next = NULL;

        p->next = new;
        p = p->next;
    }
    result = result->next;
    return result;
}