【LeetCode】2. Add Two Numbers

Question link

Link

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;
}