题解 | #链表相加(二)#

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */

/**
 * 
 * @param head1 ListNode类 
 * @param head2 ListNode类 
 * @return ListNode类
 */
#先反转链表，再竖式相加
#include<stdlib.h>
struct ListNode * reverseListnode(struct ListNode *head)
{
    struct ListNode  *p, *q, *temp;
    if(head ==NULL) return NULL;
    if(head->next == NULL) return head;
    p = head;
    q = head->next;
    head->next = NULL;
    while(q != NULL)
    {
        temp = q->next;
        q->next = p;
        p = q;
        q = temp;
    }
    return p;
}
struct ListNode* addInList(struct ListNode* head1, struct ListNode* head2 ) {
    // write code here
    if(head1 == NULL && head2 == NULL) return NULL;
    struct ListNode *tail1, *tail2;
    tail1 = reverseListnode(head1);
    tail2 = reverseListnode(head2);
    int flag=0;
    struct ListNode  *p, *q, *head, *temp;
    p = tail1;
    q = tail2;
    temp = NULL;
    while(p != NULL && q != NULL)
    {
        head = (struct ListNode *) malloc(sizeof(struct ListNode));
        head->val = p->val + q->val;
        if(flag) 
        {
            head->val ++;
            flag = 0;
        }
        if(head->val > 9)
        {
            head->val = head ->val -10;
            flag = 1;
        }
        head->next = temp;
        temp = head;
        p = p->next;
        q = q->next;
    }
    while(p != NULL)
    {
        head = (struct ListNode *) malloc(sizeof(struct ListNode));
        head->val = p->val;
        if(flag) 
        {
            head->val ++;
            flag = 0;
        }
        if(head->val > 9)
        {
            head->val = head ->val -10;
            flag = 1;
        }
        head->next = temp;
        temp = head;
        p = p->next;
    }
    while(q != NULL)
    {
        head = (struct ListNode *) malloc(sizeof(struct ListNode));
        head->val = q->val;
        if(flag) 
        {
            head->val ++;
            flag = 0;
        }
        if(head->val > 9)
        {
            head->val = head ->val -10;
            flag = 1;
        }
        head->next = temp;
        temp = head;
        q = q->next;
    }
    if(flag) 
    {
        head = (struct ListNode *) malloc(sizeof(struct ListNode));
        head->val = 1;
        head->next = temp;
    }
    tail1->next = NULL;
    tail2->next = NULL;
    return head;
}