链表相加(二)

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

struct ListNode* addInList(struct ListNode* head1, struct ListNode* head2 ) {
    // write code here
    int len1, len2, i, j, min = 0;
    len1 = lenth(head1);
    len2 = lenth(head2);
    int* addend1 = (int*)calloc(len1, sizeof(int));
    int* addend2 = (int*)calloc(len2, sizeof(int));
    int* sum = (int*)calloc(len1+len2, sizeof(int));
    struct ListNode* p1 = head1, *p2 = head2;
    //将两个加数放入对应数组
    for(i = len1 - 1; i >= 0; i--){
        addend1[i] = p1->val;
        p1 = p1->next;
    }
    for(i = len2 - 1; i >= 0; i--){
        addend2[i] = p2->val;
        p2 = p2->next;
    }
    p1 = head1;
    p2 = head2;
    //合并两个链表
    while(p1->next != NULL){
        p1 = p1->next;
    }
    p1->next = p2;
    p1 = head1;
    //单个计算对应位加和放入sum数组
    if(len1 <= len2){
        min = len1;

    }else{
        min = len2;
    }
    for(i = 0; i < min; i++){
        sum[i] = addend1[i] + addend2[i];
    }
    j = i;
    while(j != len1){
        sum[j] = addend1[j];
        j++;
    }
    j = i;
    while(j != len2){
        sum[j] = addend2[j];
        j++;
    }
    //遍历数组，若发现本位和/10 == 1 说明有进位flag，默认没有进位
    int flag = 0;
    for(i = 0; i < len1 + len2; i++){
        sum[i] += flag;
        if(sum[i] / 10 == 1){
            flag = 1;
            sum[i] = sum[i] % 10;
        }else{
            flag = 0;
        }
    }
    int dir = 0;//第一个不为0的位置（从0开始）
    i = len1 + len2 -1;
    while(i >= 0){
        if(sum[i] == 0){
            i--;
        }else{
            dir = i;
            break;
        }
    }
    i = dir;
    while(i >= 0){
        p1->val = sum[i];
        if(i == 0){
            p1->next = NULL;
        }else{
            p1 = p1->next;
        }  
        i--;
    }

    return head1;
}

struct ListNode* ReverseList(struct ListNode* head ) {
    struct ListNode *p,*res;
    if((head==NULL) || (head->next==NULL))
        return head;
    p = head->next;
    res = ReverseList(p);
    p->next = head;
    p->next->next = NULL;
    return res;
}
struct ListNode* addInList(struct ListNode* head1, struct ListNode* head2 ) {
    struct ListNode *p,*p1,*p2,*res=NULL;
    int carry=0;

    p1 = ReverseList(head1);
    p2 = ReverseList(head2);

    while(p1!=NULL || p2!=NULL) {
        int t;
        t = (p1==NULL?0:p1->val)+(p2==NULL?0:p2->val)+carry;
        if(t>9) {
            carry = t/10;
            t %= 10;
        }
        else 
            carry = 0;
        
        if(res==NULL) {
            res = (struct ListNode *)malloc(sizeof(struct ListNode));
            res->val = t;
            res->next = NULL;
            p = res;
        }
        else {
            struct ListNode *NewNode;
            NewNode = (struct ListNode *)malloc(sizeof(struct ListNode));
            NewNode->val = t;
            NewNode->next = NULL;
            p->next = NewNode;
            p = p->next;
        }
        
        if(p1!=NULL)
            p1 = p1->next;
        if(p2!=NULL)
            p2 = p2->next;
    };

    res = ReverseList(res);
    return res;
}

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */

/**
 * 
 * @param head1 ListNode类 
 * @param head2 ListNode类 
 * @return ListNode类
 */
 #include <math.h>
#include <stdio.h>
#include <stdlib.h>
struct ListNode* ReverseList(struct ListNode* pHead );
struct ListNode* addInList(struct ListNode* head1, struct ListNode* head2 ) {
    // write code here
    int i = 0;
    struct ListNode *Head1 = ReverseList(head1);
    struct ListNode *Head2 = ReverseList(head2);
    struct ListNode *p = (struct ListNode *)malloc( sizeof(struct ListNode) );
    struct ListNode *n,*Head = p;
    p->next=NULL;
    while (Head1&&Head2) {
        n = (struct ListNode *)malloc( sizeof(struct ListNode) );
        if((Head1->val + Head2->val + i)>=10)
        {
        n->val=(Head1->val + Head2->val + i)-10;
        i=1;
        }
        else 
        {
        n->val=(Head1->val + Head2->val + i);
        i=0;
        }
        n->next=NULL;
        p->next=n;
        p=n;
        Head1 = Head1->next;
        Head2 = Head2->next;
    }
    if (i==0)
        {   
            if (Head1) {
            p->next=Head1;
            }
            else if (Head2){
            p->next=Head2;
            }
            else;
        }
    while (Head1&&i)
    {   
        n = (struct ListNode *)malloc( sizeof(struct ListNode) );
        if((Head1->val + i)>=10)
        {
        n->val=(Head1->val + i)-10;
        i=1;
        n->next=NULL;
        p->next=n;
        p=n;
        Head1 = Head1->next;
        }
        else
        {
        n->val=(Head1->val + i);
        i=0;
        p->next=n;
        p=n;
        p->next=Head1->next;
        }
    }
     while (Head2&&i)
    {   
        n = (struct ListNode *)malloc( sizeof(struct ListNode) );
        if((Head2->val + i)>=10)
        {
        n->val=(Head2->val + i)-10;
        i=1;
        n->next=NULL;
        p->next = n;
        p = n;
        Head2 = Head2->next;
        }
        else
        {
        n->val=(Head2->val + i);
        i=0;
        p->next=n;
        p=n;
        p->next=Head2->next;
        }
       
    }
    if (i==1) {
        n = (struct ListNode *)malloc( sizeof(struct ListNode) );
        n->val=1;
        n->next=NULL;
        p->next = n;
        p = n;
    }
    
    return ReverseList(Head->next);
}
 struct ListNode* ReverseList(struct ListNode* pHead )
 {
    // write code here
    if(pHead==NULL||pHead->next==NULL){
        return pHead;
    }
    struct ListNode *cur = NULL;
   cur = pHead;
   struct ListNode *pre = NULL;
   struct ListNode *temp;
   while (cur) {
        temp = cur->next;
        cur->next=pre;
        pre = cur;
        cur = temp;
   }
    return pre;
}

struct ListNode* reverse(struct ListNode* head){
    struct ListNode* p1 = head->next;
    struct ListNode* p2 = p1->next;
    head->next = NULL;
    while(p1){
        p1->next = head;
        head = p1;
        p1 = p2;
        if(p1)
            p2 = p1->next;
    }
    return head;
}

struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2){
    struct ListNode* head1 = l1;
    struct ListNode* head2 = l2;
    struct ListNode* tail;
    while(head1 && head2){
        tail = head1;
        head1->val = head1->val + head2->val;
        if(head1->val >= 10 && head1->next){
            head1->val %= 10;
            head1->next->val++; 
        }
        else if(head1->val >= 10 && head2->next){
            head1->val %= 10;
            head2->next->val++;
            head1->next = head2->next;
            head2->next = NULL;
        }
        else if(head1->val >= 10){
            head1->val %= 10;
            l2->val = 1;
            tail->next = l2;
            l2->next = NULL;
        }
        head1 = head1->next;
        head2 = head2->next;
    }
    while(head1){
        if(head1->val >= 10){
            head1->val %= 10;
            if(head1->next)
                head1->next->val++;
            else{
                l2->val = 1;
                head1->next = l2;
                l2->next = NULL;
            }
        }
        head1 = head1->next;
    }
    while(head2)
    {
        tail->next = head2;
        head2 = NULL; 
    }
    return l1;
}

struct ListNode* addInList(struct ListNode* head1, struct ListNode* head2 ){
    if(head1->val == 0)
        return head2;
    if(head2->val == 0)
        return head1;
    if(head1->next)
        head1 = reverse(head1);//逆置
    if(head2->next)
        head2 = reverse(head2);//逆置
    struct ListNode* head3;
    head3 = addTwoNumbers(head1, head2);//相加
    if(head3->next)
        head3 = reverse(head3);//结果逆置回来
    return head3;
}

struct ListNode* ReverseList(struct ListNode* pHead ) 
{
    struct ListNode *p = pHead;
    struct ListNode *q = NULL;
    struct ListNode *temp = NULL;
    while(p)
    {
        temp = q;
        q = p;
        p = p->next;
        q->next = temp;
    }
    // write code here
    return q;
}
/**
 * 
 * @param head1 ListNode类 
 * @param head2 ListNode类 
 * @return ListNode类
 */
struct ListNode* addInList(struct ListNode* head1, struct ListNode* head2 ) 
{
    struct ListNode *p = ReverseList(head1);
    struct ListNode *newhead = p;
    struct ListNode *q = ReverseList(head2);
    struct ListNode *temp = NULL;
    int jin = 0;
    while(p && q)
	{
		if(p->val + q->val + jin <= 9)
		{
			p->val = p->val + q->val + jin;
			jin = 0;
		}
		else
		{
			p->val = (p->val + q->val +jin)%10;
			jin = 1;
		}
        temp = p;
		p = p->next;
		q = q->next;
	}
	while(p || q || jin)
	{
		if(p)
		{
			if(p->val +jin <= 9)
			{
				p->val = p->val +jin;
				jin = 0;
			}
			else
			{
				p->val = 0;
				jin = 1;
			}
            temp = p;
            p = p->next;
		}
		else if(q)
		{
			struct ListNode * newp = (struct ListNode *)malloc(sizeof(struct ListNode));
			temp->next = newp;	//	最后一个结点的下一个 是 新结点
			newp->next = NULL;
			if(q->val +jin <= 9)
			{
				newp->val = q->val +jin;
				jin = 0;
				
			}
			else
			{
				newp->val = 0;
				jin = 1;
			}
            temp = newp;
            q = q->next;
		}
		else if(jin)
		{
			struct ListNode * newp = (struct ListNode *)malloc(sizeof(struct ListNode));
			temp->next = newp;	//	最后一个结点的下一个 是 新结点
			newp->next = NULL;
			newp->val = jin;
			jin = 0;
		}
	}
    return ReverseList(newhead);
    // write code here
}

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

/**
 * 
 * @param head1 ListNode类 
 * @param head2 ListNode类 
 * @return ListNode类
 */
#先反转链表，再竖式相加
#include<stdlib.h>
struct ListNode * reverseListnode(struct ListNode *head)
{
    struct ListNode  *p, *q, *temp;
    if(head ==NULL) return NULL;
    if(head->next == NULL) return head;
    p = head;
    q = head->next;
    head->next = NULL;
    while(q != NULL)
    {
        temp = q->next;
        q->next = p;
        p = q;
        q = temp;
    }
    return p;
}
struct ListNode* addInList(struct ListNode* head1, struct ListNode* head2 ) {
    // write code here
    if(head1 == NULL && head2 == NULL) return NULL;
    struct ListNode *tail1, *tail2;
    tail1 = reverseListnode(head1);
    tail2 = reverseListnode(head2);
    int flag=0;
    struct ListNode  *p, *q, *head, *temp;
    p = tail1;
    q = tail2;
    temp = NULL;
    while(p != NULL && q != NULL)
    {
        head = (struct ListNode *) malloc(sizeof(struct ListNode));
        head->val = p->val + q->val;
        if(flag) 
        {
            head->val ++;
            flag = 0;
        }
        if(head->val > 9)
        {
            head->val = head ->val -10;
            flag = 1;
        }
        head->next = temp;
        temp = head;
        p = p->next;
        q = q->next;
    }
    while(p != NULL)
    {
        head = (struct ListNode *) malloc(sizeof(struct ListNode));
        head->val = p->val;
        if(flag) 
        {
            head->val ++;
            flag = 0;
        }
        if(head->val > 9)
        {
            head->val = head ->val -10;
            flag = 1;
        }
        head->next = temp;
        temp = head;
        p = p->next;
    }
    while(q != NULL)
    {
        head = (struct ListNode *) malloc(sizeof(struct ListNode));
        head->val = q->val;
        if(flag) 
        {
            head->val ++;
            flag = 0;
        }
        if(head->val > 9)
        {
            head->val = head ->val -10;
            flag = 1;
        }
        head->next = temp;
        temp = head;
        q = q->next;
    }
    if(flag) 
    {
        head = (struct ListNode *) malloc(sizeof(struct ListNode));
        head->val = 1;
        head->next = temp;
    }
    tail1->next = NULL;
    tail2->next = NULL;
    return head;
}

struct ListNode* addInList(struct ListNode* head1, struct ListNode* head2 ) {
    //相加是从低位向高位进位 设置一个进位表示CFlag
    //用头插法改变读取顺序 再在第二次复原时使用头插法恢复
    int i,j,k;
    struct ListNode *p1,*p2,*head3,*newnode,*work1,*work2;
    int Cflag=0;
    i=0;j=0;
    p1=head1;p2=head2;
        while(p1!=NULL){
            i++;p1=p1->next;
        }
         while(p2!=NULL){
            j++;p2=p2->next;
        }
    p1=head1;p2=head2;
    head3=NULL;
    newnode=(struct ListNode*)malloc(sizeof(struct ListNode));
        if(i>j){
            k=i-j;
            while(k!=0){
            newnode->val=p1->val;
            p1=p1->next;
            newnode->next=head3;
            head3=newnode;
            newnode=(struct ListNode*)malloc(sizeof(struct ListNode));
            k--;
            }}
         if(j>i){
             k=j-i;
            while(k!=0){
            newnode->val=p2->val;
            p2=p2->next;
            newnode->next=head3;
            head3=newnode;
            newnode=(struct ListNode*)malloc(sizeof(struct ListNode));
            k--;
            }}
        while(p1&&p2){
            newnode->val=p1->val+p2->val;
            newnode->next=head3;
            head3=newnode;
            newnode=(struct ListNode*)malloc(sizeof(struct ListNode));
            p1=p1->next;p2=p2->next;
        }
    //逆置的链表生成了 使用Cflag记录进位 使用头插再次逆置；
    work1=head3;
    head3=NULL;
    while(work1){
        if(Cflag==1){
        work1->val+=1;
        Cflag=0;
        }
        if(work1->val>9){
            work1->val=work1->val%10;
            Cflag=1;
        }
        work2=work1->next;
        work1->next=head3;
        head3=work1;
        work1=work2;
    }
         if(Cflag){
             newnode->val=1;
             newnode->next=head3;
             head3=newnode;
         }
         return head3;
    }