C语言重构【2】两数相加

太过爱你忘了你带给我的痛 2022-12-22 09:45 125阅读 0赞

### 文章目录 ###

*   *   *   *  所有题目源代码：\[Git地址\](https://github.com/ch98road/leetcode)
             *  题目
             *  方案：
             *   *  复杂度计算

#### 所有题目源代码：[Git地址][Git] ####

#### 题目 ####

给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
    
    如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
    
    您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
    
    示例：
    
    输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
    输出：7 -> 0 -> 8
    原因：342 + 465 = 807

#### 方案： ####

*  他的数是倒过来放的，故很方便相加，就是需要考虑进位的问题

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */
    class Solution
    { 
    public:
        ListNode *addTwoNumbers(ListNode *l1, ListNode *l2)
        { 
            ListNode *head = l1;
            int add = 0;
            while (l1 != NULL && l2 != NULL)
            { 
                l1->val += l2->val + add;
                if (add == 1)
                    l1->val++;
                if (l1->val >= 10)
                { 
                    l1->val -= 10;
                    add = 1;
                }
                else
                { 
                    add = 0;
                }
                if (l1->next == NULL)
                { 
                    l1->next = l2->next;
                    //接上l2还是null的话就到底了，此时的进位必须新建节点了
                    if (l1->next == NULL && add == 1)
                    { 
                        l1->next = new ListNode(1);
                        add = 0;
                    }
                    l1 = l1->next;
                    break;
                }
                else
                { 
                    l2 = l2->next;
                    l1 = l1->next;
                }
            }
    
            //解决不等长问题
            while (l1 != NULL && add == 1)
            { 
                l1->val++;
                if (l1->val >= 10)
                { 
                    l1->val -= 10;
                    add = 1;
                }
                else
                { 
                    add = 0;
                }
                if (l1->next == NULL && add == 1)
                { 
                    l1->next = new ListNode(1);
                    break;
                }
                else
                { 
                    l1 = l1->next;
                }
            }
            return head;
        }
    };

##### 复杂度计算 #####

*  时间复杂度：O(n)
 *  空间复杂度：O(1)

[Git]: https://github.com/ch98road/leetcode