题解 | 链表相加(二)

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param head1 ListNode类 
 * @param head2 ListNode类 
 * @return ListNode类
 */
#include <stdlib.h>

struct ListNode* reList(struct ListNode* head){
    struct ListNode* q, * p = head->next;
    head->next = NULL;
    while(p){
        q=p;
        p=p->next;
        q->next=head->next;
        head->next=q;
    }
    return head;
}

struct ListNode* addInList(struct ListNode* head1, struct ListNode* head2 ) {
    struct ListNode* head = (struct ListNode*)malloc(sizeof(struct ListNode));
    head->next = NULL;

    // 逆置两个链表
    struct ListNode* dummy1 = (struct ListNode*)malloc(sizeof(struct ListNode));
    dummy1->next = head1;
    struct ListNode* dummy2 = (struct ListNode*)malloc(sizeof(struct ListNode));
    dummy2->next = head2;
    head1 = reList(dummy1)->next;
    head2 = reList(dummy2)->next;

    // 相加
    int sum;
    int jin=0;
    while(head1!=NULL || head2!=NULL){

        sum = (head1==NULL?0:head1->val)+(head2==NULL?0:head2->val)+jin;
        if(sum >= 10){
            jin = sum/10;
            sum = sum%10;
        }else{
            jin = 0;
        }

        if(head1)
            head1 = head1->next;
        if(head2)    
            head2 = head2->next;

        // 存储，使用前插法，就不需要逆置了（但是内存超出了限制）
        struct ListNode* p = (struct ListNode*)malloc(sizeof(struct ListNode));
        p->val = sum;
        p->next = head->next;
        head->next = p;

    }

    return head->next;
    
}