题解 | #两个链表生成相加链表#

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

/**
 * 
 * @param head1 ListNode类 
 * @param head2 ListNode类 
 * @return ListNode类
 */

/*
1.先将链表进行反转，然后按每个节点进行计算
*/
struct ListNode* ReverseList(struct ListNode* pHead){
    struct ListNode* tmp = NULL;
    struct ListNode* save = NULL;
    struct ListNode* ReverseList = pHead;
    struct ListNode* p = pHead;
    
    if(pHead == NULL)
        return pHead;
    while(p != NULL){
        save = p->next;
        p->next = tmp;
        tmp = p;
        p = save;
    }
    ReverseList = tmp;
    return ReverseList;
}

// struct ListNode* addInList(struct ListNode* head1, struct ListNode* head2 ) {
//     // write code here
//     struct ListNode* Head;
//     struct ListNode* L1 = head1;
//     struct ListNode* L2 = head2;
//     struct ListNode* p = L1;
//     struct ListNode* q = L2;
//     struct ListNode* s;
//     struct ListNode* tmp = NULL;
//     int remainder = 0;
//     int p_val = 0;
//     int q_val = 0;
    
//   if(head1 == NULL && head2 != NULL)
//         return head2;
//   if(head2 == NULL && head1 != NULL)
//         return head1;
//     L1 = ReverseList(head1);
//     L2 = ReverseList(head2);
//     p = L1;
//     q = L2;
//     /*头插法 创建节点*/
// while(p != NULL || q != NULL){
//         /* 创建节点并为该节点赋值*/
//     remainder = 0; //remainder 用来存放进位数据
//     if(p != NULL){
//         remainder += p->val;
//         p = p->next;
//     }
//     if(q != NULL){
//         remainder += q->val;
//         q = q->next;
//     }
//     s = (struct ListNode*)malloc(sizeof(struct ListNode));
//     s->val = 0;
//     s->next = NULL;
// //     if(p->val + q->val +remainder> 10){
// //         remainder = 1;
// //         //s->val = (p->val + q->val)%10;
// //     }
// //     if((p->val + q->val + remainder)%10 == 0){
// //         remainder = 1;
// //         s->val = 0;
// //     }
// //     if((p->val + q->val + remainder) < 10){
// //         remainder = 0;
// //         s->val = p->val + q->val + remainder;
// //     }
// //         s->next = tmp;
// //         tmp = s;
// //         p = p->next;
// //         q = q->next;
// //     }
// //      /* 如果p->next 或者 q->next有一个 == NULL*/
// //     if(p->val + q->val + remainder >= 10){
// //         s = (struct ListNode*)malloc(sizeof(struct ListNode));
// //         s->val = (p->val + q->val + remainder)%10;
// //         s->next = tmp;
// //         tmp = s;
// //         s = (struct ListNode*)malloc(sizeof(struct ListNode));
// //         s->val = 1;
// //         s->next = tmp;
// //         tmp = s;
// //     }
// //       while(p != NULL || q != NULL){
// //           if(p->val + q->val + remainder < 10){
// //               if(p->next != NULL || q->next != NULL || p != NULL || q != NULL){
// //                     s = (struct ListNode*)malloc(sizeof(struct ListNode));
// //                     s->val = (p->val + q->val + remainder) %10;
// //                     s->next = tmp;
// //                     tmp = s;    
// //               }
// //         }
// //         if(p->val + q->val + remainder == 10){    //如果节点相加大于10， remainder = 1
// //             if(p->next != NULL || q->next != NULL || p != NULL || q != NULL){
// //                     s = (struct ListNode*)malloc(sizeof(struct ListNode));
// //                     s->val = (p->val + q->val + remainder) %10;
// //                     s->next = tmp;
// //                     tmp = s;
// //             }
// //             remainder = 1;
// //             p = p->next;
// //             q = q->next;
    
//     //求出进位
//     remainder = 
    
//     }
//     Head = tmp;
//     return Head;
// }
struct ListNode* addInList(struct ListNode* head1, struct ListNode* head2 ) {
    // write code here
    struct ListNode* Head;
    struct ListNode* L1 = head1;
    struct ListNode* L2 = head2;
    struct ListNode* p = L1;
    struct ListNode* q = L2;
    struct ListNode* s;
    struct ListNode* NewHead ;
    struct ListNode* TempNode;
    int remainder = 0;
    int p_val = 0;
    int q_val = 0;
    
  if(head1 == NULL && head2 != NULL)
        return head2;
  if(head2 == NULL && head1 != NULL)
        return head1;
    L1 = ReverseList(head1);
    L2 = ReverseList(head2);
    p = L1;
    q = L2;
    /*头插法 创建节点*/
    int tmp = 0;
    NewHead = (struct ListNode*)malloc(sizeof(struct ListNode));
    TempNode = NewHead;
while(p != NULL || q != NULL){
            /* 创建节点并为该节点赋值*/
       //remainder用来累加此时的数值(加数+加数+上一位的进位)
        int remainder = tmp;
        //当节点不为空的时候，则需要加上当前节点的值
        if(p != NULL){
            remainder += p->val;
            p = p->next;
        }
        if(q != NULL){
            remainder += q->val;
            q = q->next;
        }
        //求出进位
        tmp = remainder/10;
        //进位后剩下的数值即为当前节点的数值
        s = (struct ListNode*)malloc(sizeof(struct ListNode));
        s->val = remainder%10;
        TempNode->next = s;
        TempNode = s;
    }
    
    //最后当两条链表都加完的时候，进位不为0的时候，则需要再加上这个进位
    if(tmp > 0){
        s = (struct ListNode*)malloc(sizeof(struct ListNode));
    }
    
    //重新翻转链表
    TempNode = NewHead;
    NewHead = NewHead->next;
    TempNode->next = NULL;
    free(TempNode);
    NewHead = ReverseList(NewHead);
    return NewHead;

    
//     if(p->val + q->val +remainder> 10){
//         remainder = 1;
//         //s->val = (p->val + q->val)%10;
//     }
//     if((p->val + q->val + remainder)%10 == 0){
//         remainder = 1;
//         s->val = 0;
//     }
//     if((p->val + q->val + remainder) < 10){
//         remainder = 0;
//         s->val = p->val + q->val + remainder;
//     }
//         s->next = tmp;
//         tmp = s;
//         p = p->next;
//         q = q->next;
//     }
//      /* 如果p->next 或者 q->next有一个 == NULL*/
//     if(p->val + q->val + remainder >= 10){
//         s = (struct ListNode*)malloc(sizeof(struct ListNode));
//         s->val = (p->val + q->val + remainder)%10;
//         s->next = tmp;
//         tmp = s;
//         s = (struct ListNode*)malloc(sizeof(struct ListNode));
//         s->val = 1;
//         s->next = tmp;
//         tmp = s;
//     }
//       while(p != NULL || q != NULL){
//           if(p->val + q->val + remainder < 10){
//               if(p->next != NULL || q->next != NULL || p != NULL || q != NULL){
//                     s = (struct ListNode*)malloc(sizeof(struct ListNode));
//                     s->val = (p->val + q->val + remainder) %10;
//                     s->next = tmp;
//                     tmp = s;    
//               }
//         }
//         if(p->val + q->val + remainder == 10){    //如果节点相加大于10， remainder = 1
//             if(p->next != NULL || q->next != NULL || p != NULL || q != NULL){
//                     s = (struct ListNode*)malloc(sizeof(struct ListNode));
//                     s->val = (p->val + q->val + remainder) %10;
//                     s->next = tmp;
//                     tmp = s;
//             }
//             remainder = 1;
//             p = p->next;
//             q = q->next;
    
    
//     }
//     Head = tmp;
//     return Head;
}