力扣算法题-2.两数相加 C语言实现

题目

给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。

如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例：

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4) 输出：7 -> 0 -> 8 原因：342 + 465 = 807

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/add-two-numbers

思路

题目很简单，但是为了达到内存占用最小的效果， 使用题目中给出的链表节点，若最后仍有进位，则申请一下最后一个节点的内存即可。

程序

/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2){ int carry = 0; struct ListNode* head = NULL; struct ListNode* b = NULL; struct ListNode* pre = NULL; /*两个链表没有遍历完全 或者 存在进位的情况 则执行循环 */ while(!(l1 == NULL && l2 == NULL) || carry){ /*尽量先使用原有节点，节省内存*/ b = l1 == NULL ? l2 : l1; /*若b为空（最后进位的情况），则分配节点内存*/ if(b == NULL){ b = (struct ListNode*)malloc(sizeof(struct ListNode)); b->val = 0; b->next = NULL; } /*计算节点值*/ b->val = (l1==NULL?0:l1->val) + (l2==NULL?0:l2->val) + carry; carry = b->val > 9 ? 1 : 0; b->val = carry == 1 ? b->val - 10 : b->val; /*链表头赋值*/ head = head == NULL ? b : head; /*节点前后指向处理*/ if(pre != NULL){ pre->next = b; } pre = b; /*遍历原有链表*/ l1 = (l1==NULL?NULL:l1->next); l2 = (l2==NULL?NULL:l2->next); } return head; }