首页 > 代码库 > [LeetCode]2. Add Two Numbers
[LeetCode]2. Add Two Numbers
You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
根据给定的两个非负数组成的链表，对链表相应位值相加后组成一个新的链表，并返回。若相加和大于等于10，则该节点值为减10后的差，并向后一节点进一。
解题：
1）若传入两链表为空，则返回空链表；若链表l1为空，则直接返回链表l2即可；若链表l2位空，则直接返回链表l1即可
2）若两链表都不为空，则同时进行递增，直到有一个链表为空为止。
3）若一个链表为空，另一链表不为空，则递增不为空链表，直到为空。
4）最后检查最后一个节点是否有进位，若有，则再新增相应节点。否则，返回链表。
说明：
1）flag定义为进位值，若和大于等于10，则flag置1，否则flag置0.
2）head指向头节点，last指向尾节点。
3）新增节点时，先将last节点的next指向新增节点。再把新增节点赋值给last.
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
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;
}
int flag = 0;
struct ListNode *head = NULL;
struct ListNode *last = head;
while ( l1 != NULL && l2 != NULL )
{
int val = 0;
struct ListNode *node = NULL;
node = (struct ListNode *)malloc(sizeof(struct ListNode *));
if ( node == NULL )
{
return head;
}
val = l1->val + l2->val + flag;
if ( val >= 10 )
{
val -= 10;
flag = 1;
}
else
{
flag = 0;
}
node->val = val;
node->next = NULL;
if ( head == NULL )
{
head = node;
last = head;
}
else
{
last->next = node;
last = node;
}
l1 = l1->next;
l2 = l2->next;
}
while ( l1 == NULL && l2 != NULL )
{
int val = 0;
struct ListNode *node = NULL;
node = (struct ListNode *)malloc(sizeof(struct ListNode *));
if ( node == NULL )
{
return head;
}
val = l2->val + flag;
if ( val >= 10 )
{
val -= 10;
flag = 1;
}
else
{
flag = 0;
}
node->val = val;
node->next = NULL;
last->next = node;
last = node;
l2 = l2->next;
}
while ( l1 != NULL && l2 == NULL )
{
int val = 0;
struct ListNode *node = NULL;
node = (struct ListNode *)malloc(sizeof(struct ListNode *));
if ( node == NULL )
{
return head;
}
val = l1->val + flag;
if ( val >= 10 )
{
val -= 10;
flag = 1;
}
else
{
flag = 0;
}
node->val = val;
node->next = NULL;
last->next = node;
last = node;
l1 = l1->next;
}
if ( l1 == NULL && l2 == NULL && flag == 1 )
{
struct ListNode *node = NULL;
node = (struct ListNode *)malloc(sizeof(struct ListNode *));
if ( node == NULL )
{
return head;
}
node->val = 1;
node->next = NULL;
last->next = node;
last = node;
}
return head;
}[LeetCode]2. Add Two Numbers
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。