LeetCode – Add Two Numbers

题目:

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

发表回复