[LeetCode C实现]2. 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.
最开始的解法，有种很直的直男的感觉，要多直有多直的感觉，思路就是判断两个链表非空，两个链表其中一个为空，最后一种情形是都空。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2)
{
    struct ListNode* p1 = l1;
    struct ListNode* p2 = l2;
    struct ListNode* ret = (struct ListNode*)malloc(sizeof(struct ListNode));
    
    struct ListNode* p = NULL;
    /*进位标识*/
    int carry = 0;
    
    while (p1 != NULL || p2 != NULL ) 
    {
        /*首次循环p指向外面申请的内存*/
        if (p == NULL) 
        {
            p = ret;
        }
        else 
        {
            p->next = (struct ListNode*)malloc(sizeof(struct ListNode));
            p = p->next;
        }
        
        /*l1和l2均非空*/
        if((NULL != p1)&&(NULL != p2))
        {
            int a = p1->val;
            int b = p2->val;
            int s = (a + b + carry) % 10;
            carry = (a + b + carry) / 10;
            p->val = s;
            p->next = NULL;
            p1 = p1->next;
            p2 = p2->next;
            
        }
        /*链表l1非空,l2为空*/
        else if((NULL == p2)&&(p1 != NULL))
        {
            
            int a = 0;
            int b = p1->val;
            int s = (a + b + carry) % 10;
            carry = (a + b + carry) / 10;
            p->val = s;
            p->next = NULL;
            p1 = p1->next;
        }
        /*链表l1为NULL,l2非空*/
        else if((NULL == p1)&&(p2 != NULL))
        {
            int a = 0;
            int b = p2->val;
            int s = (a + b + carry) % 10;
            carry = (a + b + carry) / 10;
            p->val = s;
            p->next = NULL;
            p2 = p2->next;
        
        }
        /*p1 p2均为NULL*/
        else
        {
            break;
        }
        
        
    }
    
    /*处理50+50 = 100,和的位数多一位的情况*/
    if(carry)
    {
        p->next = (struct ListNode*)malloc(sizeof(struct ListNode));
        /*进位只能为1*/
        p->next->val = 1;
        p->next->next = NULL;
    }
    
    return ret;
}

后面发现可以将三种情况写在一个逻辑里面，代码如下：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2)
{
    struct ListNode* p1 = l1;
    struct ListNode* p2 = l2;
    struct ListNode* ret = (struct ListNode*)malloc(sizeof(struct ListNode));
    
    struct ListNode* p = NULL;
    /*进位标识*/
    int carry = 0;
    
    while (p1 != NULL || p2 != NULL ) 
    {
        /*首次循环p指向外面申请的内存*/
        if (p == NULL) 
        {
            p = ret;
        }
        else 
        {
            p->next = (struct ListNode*)malloc(sizeof(struct ListNode));
            p->next->val = 0;
            p = p->next;
        }
        /*考虑两个链表 长短不一致问题，短的链表值赋为0*/
        int a = (p1 != NULL)? p1->val : 0;
        int b = (p2 != NULL)? p2->val : 0;
        int s = (a + b + carry) % 10;
        carry = (a + b + carry) / 10;
        p->val = s;
        p->next = NULL;
        
        p1 = (p1 == NULL)? NULL : p1->next;
        p2 = (p2 == NULL)? NULL : p2->next;
    }
    
    /*处理50+50 = 100,位数变化的情况*/
    if(carry)
    {
        p->next = (struct ListNode*)malloc(sizeof(struct ListNode));
        /*进位只能为1*/
        p->next->val = 1;
        p->next->next = NULL;
    }
    
    return ret;
}

接着我们发现处理两个数相加结果多了一位的情形可以和主逻辑合并在一起。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2)
{
    struct ListNode* p1 = l1;
    struct ListNode* p2 = l2;
    struct ListNode* ret = (struct ListNode*)malloc(sizeof(struct ListNode));
    
    struct ListNode* p = NULL;
    /*进位标识*/
    int carry = 0;
    
    while (p1 != NULL || p2 != NULL || carry) 
    {
        /*首次循环p指向外面申请的内存*/
        if (p == NULL) 
        {
            p = ret;
        }
        else 
        {
            p->next = (struct ListNode*)malloc(sizeof(struct ListNode));
            p->next->val = 0;
            p = p->next;
        }
        /*考虑两个链表 长短不一致问题，短的链表值赋为0*/
        int a = (p1 != NULL)? p1->val : 0;
        int b = (p2 != NULL)? p2->val : 0;
        int s = (a + b + carry) % 10;
        carry = (a + b + carry) / 10;
        p->val = s;
        p->next = NULL;
        
        p1 = (p1 == NULL)? NULL : p1->next;
        p2 = (p2 == NULL)? NULL : p2->next;
    }
    
    return ret;
}

52coder

[LeetCode C实现]2. Add Two Numbers