题目:
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 contain a single digit. Add the two numbers and return it as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
Example:
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4) Output: 7 -> 0 -> 8 Explanation: 342 + 465 = 807.
解题:
生成结果链表哨兵节点, 从输入两个链表的开始节点相加 再加上进位值 carry, 得到结果sum, sum/10 存放到变量进位结果变量carry中, 将sum%/10为当前位的值,存放到链表当前节点,同时两个输入链表,结果链表移动到下一个节点操作。 循环处理直到链表遍历完毕或者进位为0,返回哨兵节点的下一个节点。
实现:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
void freelist(struct ListNode* head){
struct ListNode* p;
struct ListNode* q;
p = head;
while (p!=NULL){
q = p;
p = p->next;
free(q);
}
return ;
}
/*
inline int getmod(sum){
if(sum>=10)
return sum-10;
else
return sum;
}
inline int getrem(sum){
if(sum>=10)
return 1;
else
return 0;
}
*/
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2){
struct ListNode* head;
struct ListNode* cur;
struct ListNode* node;
head = (struct ListNode *)malloc(sizeof(struct ListNode));
if (NULL == head){
return NULL;
}
head->val=-1;
head->next = NULL;
cur = head;
int carry=0;
while (l1!=NULL || l2!=NULL ||carry){
int sum=0;
if (l1!=NULL ) {
sum +=l1->val;
}
if (l2!=NULL) {
sum +=l2->val;
}
sum += carry;
node = (struct ListNode *)malloc(sizeof(struct ListNode));
if (NULL == node){
freelist(head);
return NULL;
}
//node->val = getmod(sum);
node->val = sum % 10;
node->next = NULL;
cur->next = node;
cur=cur->next;
//carry = getrem(sum);
carry = sum / 10;
if (l1!=NULL){
l1=l1->next;
}
if (l2!=NULL){
l2=l2->next;
}
}
/*
if (carry) {
node = (struct ListNode *)malloc(sizeof(struct ListNode));
if (NULL == node){
freelist(head);
return NULL;
}
node->val = carry;
node->next = NULL;
cur->next = node;
}
*/
return head->next;
}
Be First to Comment