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

把链表内的值取出来，按照要求加完之后，再放回链表中

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

/**
 * 
 * @param head1 ListNode类 
 * @param head2 ListNode类 
 * @return ListNode类
 */
struct ListNode* addInList(struct ListNode* head1, struct ListNode* head2 ) {
    // write code here
    //遍历链表获得两个链表的长度
    struct ListNode* node1=head1;
    struct ListNode* node2=head2;
    int num_list1=0;
    while(node1){
        node1=node1->next;
        num_list1++;
    }
    int num_list2=0;
    while(node2){
        node2=node2->next;
        num_list2++;
    }
    
    //看一下哪个链表比较长，比较长的链表要用来做返回值链表
    int min_length=num_list1>num_list2?num_list2:num_list1;
    int max_length=num_list1>num_list2?num_list1:num_list2;
    struct ListNode* new_head;
    if(max_length==num_list1){
        new_head=head1;
    }else{
        new_head=head2;
    }
    
    //把两个链表中的数据拿出来做成数组
    int arry_length=max_length+1;//防止出现进位的情况，所以数组的长度比最长链表的长度多1个
    int arry1[arry_length];
    for(int j=0;j<arry_length-num_list1;j++){
        arry1[j]=0;
    }
    node1=head1;
    for(int j=arry_length-num_list1;j<arry_length;j++){
        arry1[j]=node1->val;
        node1=node1->next;
    }

    int arry2[arry_length];
    for(int j=0;j<arry_length-num_list2;j++){
        arry2[j]=0;
    }
    node2=head2;
    for(int j=arry_length-num_list2;j<arry_length;j++){
        arry2[j]=node2->val;
        node2=node2->next;
    }
    
    //翻转数组，因为本质上是翻转相加
    int temp1=0;
    for(int i=0;i<arry_length/2;i++){
        temp1=arry1[i];
        arry1[i]=arry1[arry_length-i-1];
        arry1[arry_length-i-1]=temp1;
    }
    
    int temp2=0;
    for(int i=0;i<arry_length/2;i++){
        temp2=arry2[i];
        arry2[i]=arry2[arry_length-i-1];
        arry2[arry_length-i-1]=temp2;
    }
    
    //在数组内对数据进行相加
    int j=0;
    int arry3[arry_length];
    int temp3=0;
    int temp4=0;
    while(j<=arry_length){
        temp3=arry1[j]+arry2[j]+temp4;
        if(temp3>=10){
            arry3[j]=temp3 % 10;
            temp4=1;
            arry3[j+1]=temp4;
        }
        if(temp3<10){
            arry3[j]=temp3;
            temp4=0;
        }
        j++;
    }

    //加完之后把数组反转回去
    int temp5=0;
    for(int i=0;i<arry_length/2;i++){
        temp5=arry3[i];
        arry3[i]=arry3[arry_length-i-1];
        arry3[arry_length-i-1]=temp5;
    }
     
    //将值放入链表
    if(arry3[0]==0){ //如果数组第一个数是0，说明没进位
        struct ListNode* new_node=new_head; //返回的链表的长度和输入的比较长的链表长度相同
        for(int i=1;i<=max_length;i++){ //从数组第二个值开始向后给存入链表
            new_node->val=arry3[i];
            new_node=new_node->next;
        }
    }else{ //如果数组第一个数不是0，说明有进位产生
        struct ListNode* new_node=(struct ListNode*)malloc(sizeof(struct ListNode));//有进位，则返回的链表长度比输入的最长链表长一个，新建一个结点，存第一个值
        new_node->next=new_head;//第一个结点的下一个是较长链表的头
        struct ListNode* new_head2=new_node;//把返回链表的头取出来
        for(int i=0;i<=max_length;i++){//把值存入链表
            new_node->val=arry3[i];
            new_node=new_node->next;
        }
        new_head=new_head2;
    }
    

    return new_head; 
}