题解 | NO.11#链表相加(二)#（补充）3.6

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

//反转链表函数
struct ListNode* Reverse(struct ListNode* head) {
    if (head == NULL)
        return NULL;
    struct ListNode* cur = head;
    struct ListNode* pre = NULL;
    struct ListNode* temp = NULL;
    while (cur != NULL) {
        temp = cur->next;
        cur->next = pre;
        pre = cur;
        cur = temp;
    }
    return pre;
}

struct ListNode* addInList(struct ListNode* head1, struct ListNode* head2 ) {
    //将两个链表分别反转
    head1 = Reverse(head1);
    head2 = Reverse(head2);
    int sum = 0, flag = 0;
    //建立新的链表，计算每个结点的值并链接
    //struct ListNode* res = (struct ListNode*)malloc(sizeof(struct ListNode));
    //res->val = -1;
    //struct ListNode* head = res;

    struct ListNode *head3 = NULL;
    struct ListNode *cur = NULL;

    while (head1 != NULL || head2 != NULL || flag != 0) {
        int val1 = head1 == NULL ? 0 : head1->val;
        int val2 = head2 == NULL ? 0 : head2->val;
        sum = val1 + val2 + flag;
        if (sum >= 10) {
            flag = 1;
            sum -= 10;
        } else {
            flag = 0;
        }

        cur = (struct ListNode*)malloc(sizeof(struct ListNode));
        cur->val = sum;
        cur->next = head3;
        head3 = cur;
        //head->next = (struct ListNode*)malloc(sizeof(struct ListNode));
        //采用头插法建立新链表，无需再次反转
        //head->next->val = sum;
        //head = head->next;

        if (head1 != NULL)
            head1 = head1->next;
        if (head2 != NULL)
            head2 = head2->next;
    }
    //return Reverse(res->next);
    return head3;
}

//注释部分是用的官方解析中的方法，设置哨兵结点，然后尾插法，最后返回反转后的链表
//非注释部分是我一开始想的，直接头插法创建结果链表，然后返回，是可行的