ac

假设链表中每一个节点的值都在 0 - 9 之间，那么链表整体就可以代表一个整数。
给定两个这种链表，请生成代表两个整数相加值的结果链表。
例如：链表 1 为 9->3->7，链表 2 为 6->3，最后生成新的结果链表为 1->0->0->0。

# include <bits/stdc++.h>
using namespace std;

struct list_node{
    int val;
    struct list_node * next;
};

list_node * input_list(int n)
{
    int val;
    list_node * phead = new list_node();
    list_node * cur_pnode = phead;
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &val);
        if (i == 1) {
            cur_pnode->val = val;
            cur_pnode->next = NULL;
        }
        else {
            list_node * new_pnode = new list_node();
            new_pnode->val = val;
            new_pnode->next = NULL;
            cur_pnode->next = new_pnode;
            cur_pnode = new_pnode;
        }
    }
    return phead;
}


list_node * add_list(list_node * head1, list_node * head2)
{
    //////在下面完成代码
    list_node *pHead1 = new list_node();
    list_node *pHead2 = new list_node();

    int cnt1 = 0;
    list_node *p = head1;
    while(p != NULL){
        list_node *pNext = p->next;

        p->next = pHead1->next;
        pHead1->next = p;

        p = pNext;
        cnt1 ++;
    }

    int cnt2 = 0;
    p = head2;
    while(p != NULL){
        list_node *pNext = p->next;

        p->next = pHead2->next;
        pHead2->next = p;

        p = pNext;
        cnt2 ++;
    }

    list_node *ans = new list_node();
    int indexCnt = cnt1 < cnt2 ? cnt1 : cnt2;
    int carry = 0;//进位
    list_node *p1 = pHead1->next;
    list_node *p2 = pHead2->next;
    for(int i=0;i<indexCnt;i++){
        list_node *p1Next = p1->next;
        list_node *p2Next = p2->next;

        int val = carry + p1->val + p2->val;
        if(val >= 10){
            carry = 1;
            val = val % 10;
        }else{
            carry = 0;
        }
        list_node *newNode = new list_node();
        newNode->val = val;
        newNode->next = ans->next;
        ans->next = newNode;

        p1 = p1Next;
        p2 = p2Next;
    }

    if(cnt1 > cnt2){
        while(p1 != NULL){
            list_node *p1Next = p1->next;

            int val = carry + p1->val;
            if(val >= 10){
                carry = 1;
                val = val % 10;
            }else{
                carry = 0;
            }
            list_node *newNode = new list_node();
            newNode->val = val;
            newNode->next = ans->next;
            ans->next = newNode;

            p1 = p1Next;
        }
    }

    if(cnt2 > cnt1){
        while(p2 != NULL){
            list_node *p2Next = p2->next;

            int val = carry + p2->val;
            if(val >= 10){
                carry = 1;
                val = val % 10;
            }else{
                carry = 0;
            }
            list_node *newNode = new list_node();
            newNode->val = val;
            newNode->next = ans->next;
            ans->next = newNode;

            p2 = p2Next;
        }
    }

    if(carry > 0){
        list_node *newNode = new list_node();
        newNode->val = carry;
        newNode->next = ans->next;
        ans->next = newNode;
    }
    return ans->next;
}


void print_list(list_node * head)
{
    while (head != NULL) {
        printf("%d ", head->val);
        head = head->next;
    }
    puts("");
}

int main ()
{
    int n, m;
    scanf("%d%d", &n, &m);
    list_node * head1 = input_list(n), * head2 = input_list(m);
    list_node * new_head = add_list(head1, head2);
    print_list(new_head);
    return 0;
}