leetcode 2 :两数相加

leetcode 2 :两数相加

leetcode 2 :两数相加

• 1. 题目
• 2. 示例：
• 3. 自己的解决方法
• 4. 标准答案
• • 4.1 方法一：迭代
  • 4.2 方法二：递归
  • 4.3 核心代码解释：

1. 题目

给出两个非空的链表用来表示两个非负的整数。其中，它们各自的位数是按照逆序的方式存储的，并且它们的每个节点只能存储一位数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字0之外，这两个数都不会以0开头。

2. 示例：

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

/**
* Definition for singly-linked list.
* struct ListNode {
*     int val;
*     struct ListNode *next;
* };
*/
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2){}

3. 自己的解决方法

/*整体思路：1. 判断那个链表长，然后处理短的那个长度，进行累加及进位操作如 1->2->3  4->5->6->7 先处理前3个节点，进行累加2. 公共长度处理完后，处理长的那个，并处理进位操作这里每个节点都要判断是否需要进位 如 9->9->…… 这种情况
*/
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2){/* 判空处理 */if((l1 == NULL) && (l2 == NULL)){return NULL;}if(l1 == NULL){return l2;}if(l2 == NULL){return l1;}struct ListNode* ListOne = l1;//临时指针struct ListNode* ListTwo = l2;int iCarryFlag = 0;//是否有进位标志int iLen1 = 0;//记录链表的长度int iLen2 = 0;int iListOneFlag = 0; //判断哪个链表长度最小int iListTwoFlag = 0;int iListEqualFlag = 0; //两个链表相同长度，并且最后一个节点的值大于10的处理标志int iMinLen = 0;//链表的最小长度struct ListNode* newList = NULL; //指向头结点 返回节点struct ListNode* newListTmp = NULL;  //处理节点struct ListNode* new = NULL;struct ListNode* Tmp = NULL;int iAddValue = 0; //保存两数之和/* 计算节点长度 */while(ListOne != NULL){iLen1 ++;ListOne = ListOne->next;}while(ListTwo != NULL){iLen2 ++;ListTwo = ListTwo->next;}/* 重新置位 勿忘 !!! */ListOne = l1 ;ListTwo = l2 ;/* 计算两个链表的长度，及打标记 */if(iLen1 < iLen2){iMinLen = iLen1;iListOneFlag = 1;}else if(iLen1 > iLen2){iMinLen = iLen2;iListTwoFlag = 1;}else{iMinLen = iLen1;iListEqualFlag = 1;}/* 1. 处理两个链表同长度的部分 */for(int iLoop = 1; iLoop <= iMinLen; iLoop++){if((NULL == ListOne) || (NULL == ListTwo)){return NULL;}new = (struct ListNode*)malloc(sizeof(struct ListNode));if(NULL == new){return NULL;}/* 第一个节点记录下来 */if(1 == iLoop){newListTmp = new;newList = newListTmp;}else{newListTmp->next = new;newListTmp = newListTmp->next;}new->next = NULL;//缓存累加值iAddValue = ListOne->val + ListTwo->val;if(1 == iCarryFlag){iAddValue++;}if(iAddValue >= 10) //有进位的处理{new->val = iAddValue - 10;iCarryFlag = 1;}else{new->val = iAddValue;iCarryFlag = 0; //重置}iAddValue = 0;/* 链表后移 */ListOne = ListOne->next;ListTwo = ListTwo->next;}/* 如果两个链表相同长度，并且最后一个节点大于10 的处理*/if((1 == iListEqualFlag) && (1 == iCarryFlag)){Tmp = (struct ListNode*)malloc(sizeof(struct ListNode));if(NULL == Tmp){return NULL;}Tmp->val = 1;Tmp->next = NULL;new->next = Tmp;}/* 处理剩下较长的链表操作 if(1 == iListOneFlag) 说明2长，处理链表2if(1 == iListTwoFlag) 说明1长，处理链表1	*/if(1 == iListOneFlag){while(NULL != ListTwo){if(NULL == new){return NULL;}new->next = ListTwo;/* 有进位的处理 */if(1 == iCarryFlag){ListTwo->val++;if(ListTwo->val >= 10){ListTwo->val = ListTwo->val - 10;iCarryFlag = 1;}}else{iCarryFlag = 0;}/* 链表后移 */ListTwo = ListTwo->next;new = new->next;}/* 最后再对最后一个节点值是否大于10的处理 */if(1 == iCarryFlag){Tmp = (struct ListNode*)malloc(sizeof(struct ListNode));if(NULL == Tmp){return NULL;}Tmp->val = 1;Tmp->next = NULL;new->next = Tmp;}}else if(1 == iListTwoFlag){while(NULL != ListOne){if(NULL == new){return NULL;}new->next = ListOne;/* 有进位的处理 */if(1 == iCarryFlag){ListOne->val++;if(ListOne->val >= 10){ListOne->val = ListOne->val - 10;iCarryFlag = 1;}}else{iCarryFlag = 0;}/* 链表后移 */ListOne = ListOne->next;new = new->next;}/* 最后再处理最后一个节点值是否大于10 */if(1 == iCarryFlag){Tmp = (struct ListNode*)malloc(sizeof(struct ListNode));if(NULL == Tmp){return NULL;}Tmp->val = 1;Tmp->next = NULL;new->next = Tmp;}}return newList;
}

4. 标准答案

4.1 方法一：迭代

不设置虚拟头结点:

struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2){int c = 0;if(l1 == NULL && l2 == NULL)return NULL;struct ListNode *head = (struct ListNode *)malloc(sizeof(struct ListNode));struct ListNode *cur=head;while(cur != NULL)//条件也可以写l1!=NULL||l2!=NULL||c{l1 = (l1 != NULL) ? (c += l1->val, l1->next) : l1;l2 = (l2 != NULL) ? (c += l2->val, l2->next) : l2;cur->val = c % 10;c /= 10;cur->next = (l1 != NULL || l2 != NULL || c != 0)?(struct ListNode *)malloc(sizeof(struct ListNode)) : NULL;cur = cur->next;}return head;
}

4.2 方法二：递归

int c=0;
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2){if(l1 == NULL && l2 == NULL && c == 0)return NULL;l1 = l1 != NULL ? (c += l1->val, l1->next) : l1;l2 = l2 != NULL ? (c += l2->val, l2->next) : l2;struct ListNode *cur = (struct ListNode *)malloc(sizeof(struct ListNode));cur->val = c%10;c /= 10;cur->next = addTwoNumbers(l1,l2);return cur;
}

4.3 核心代码解释：

l1=l1!=NULL?(c+=l1->val,l1->next):(c+=0,l1);
l2=l2!=NULL?(c+=l2->val,l2->next):(c+=0,l2);
c即进位,初始值0
上一位的进位(c值)加上两个链表相同位的数值,(c的个位)为当前位的结果,(c的十位)为当前位的进位

利用三目运算符:
l1不为空,说明当前位还有值,则加l1当前位的值,l1地址指向下一位
l1为空,说明l1加完了,就给进位加0(不变),l1始终不变指向空
l2同理,直到l1,l2都为空,c为0停止

作者：baal-3
链接：/