leetcode2 Add Two Numbers題解

leetcode2 Add Two Numbers題解

題的大概意思就是,輸入兩個列表,這兩個列表是兩個逆序的數,比如說1->2->4就代表421.然後將兩個鏈表翻轉後相加,存入列表中,同樣按照逆序存入列表,將其返回,剛開始題意理解錯了,WA了兩次,題目給出的一組數據比較具有迷惑性,就是243+564與432+465的結果都是807,所以剛開始我以為輸入的兩個鏈表的數正序的,只需將結果翻轉就可以了.其實這道題和大整數相加差不太多,只要考慮一下進位就沒什麼問題了.

第一版代碼如下,比較繁瑣,還有一些測試語句:

#include 
#include 
#include 

 struct ListNode {
      int val;
      ListNode *next;
      ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        int Num1[1000],Num2[1000],Sum[1000],temp[1000];//分別存儲l1,l2,l1+l2,翻轉列表時使用
        int i,j;//循環變量
        int len1,len2,len;//分別存儲len(l1),len(l2),max(len1,len2)
        int jinwei = 1;//進位的標志位

        memset(Num1,-1,sizeof(Num1));
        memset(Num2,-1,sizeof(Num2));
        memset(Sum,-1,sizeof(Sum));
        memset(temp,-1,sizeof(temp));
        
        for (i = 1;; i++)//將l1轉化為數組Num1
        {
            temp[i] = l1->val;
            if (l1->next == NULL)
            {
                break;
            }
            l1 = l1->next;
        }
        len1 = i;
        for (i = 1; i<=len1; i++)
        {
            Num1[i] = temp[len1-i+1];
           // printf(Num1:%d
,Num1[i]);
        }
        
        memset(temp,-1,sizeof(temp));

        for (i = 1;; i++)//將l2轉化為數組Num2
        {
            temp[i] = l2->val;
            if (l2->next == NULL)
            {
                break;
            }
            l2 = l2->next;
        }
        len2 = i;
        for (i = 1; i<=len2; i++)
        {
            Num2[i] = temp[len2-i+1];
           // printf(Num2:%d
,Num2[i]);
        }


        if (len2<=len1)//根據長度,將長度短的加到長度長的上面,將Num1與Num2按位相加
        {
            len = len1;
            j = len1;
            for (i = 1; i<=len1; i++)
            {
                Sum[i] = Num1[i];
            }
            for (i = len2; i>0; i--,j--)
            {
                Sum[j] = Sum[j] + Num2[i];
            }
        }
        else
        {
            len = len2;
            j = len2;
            for (i = 1; i<=len2; i++)
            {
                Sum[i] = Num2[i];
            }
            for (i = len1; i>0; i--,j--)
            {
                Sum[j] = Sum[j] + Num1[i];
            }
        }

        /*for (i = 0; i<=len; i++)
        {
            printf(Sum:%d
,Sum[i]);
        }*/

        for(i=len;i>0;i--)//處理一下Sum的進位問題
        {
            if(Sum[i-1] == -1&&(Sum[i]/10))
            {
                Sum[i-1]++;
                jinwei = 0;
            }

            Sum[i-1] += (Sum[i]/10);
            Sum[i] %= 10;
        }

        /*for (i = 0; i<=len; i++)
        {
            printf(Sum:%d
,Sum[i]);
        }*/

        ListNode head(0);
        ListNode *pre = &head;

        for(i=len;i>=jinwei;i--)//將Sum數組轉化為鏈表
        {
            pre->next = new ListNode(Sum[i]);
            pre = pre->next;
        }
        /*
        while(1)
        {
            printf(result:%d
,head.next->val);
            if (head.next->next == NULL)
        {
            break;
        }
            head.next = head.next->next;
        }*/

        return head.next;
        
    }
};



int main()
{

	/*
	ListNode list1(1);
	ListNode* p = &list1;
	p->next = new ListNode(8);
	p = p->next;
	p->next = new ListNode(4);
	p = p->next;
	p->next = new ListNode(7);
	p = p->next;
    */
	/*ListNode* test = &list1;
	while(1)
	{
		printf(%d,test->val);
		if (test->next == NULL)
		{
			break;
		}
		test = test->next;
	}*/
    ListNode list1(5);
    ListNode* p = &list1;
    p->next = new ListNode(8);

	ListNode list2(5);

	Solution tt;
	ListNode *result = tt.addTwoNumbers(&list1,&list2);
	/*while(1)
	{
		printf(%d,result->val);
		if (result->next == NULL)
		{
			break;
		}
		result = result->next;
	}*/

	return 0;
}

class Solution {
public:
    void append(ListNode* l3, int num) {
        ListNode *end = new ListNode(num);
        l3->next = end;
    }
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        int carry = 0;
        ListNode *l3 = new ListNode(0);
        ListNode *pl3 = l3;
        int a, b, c;//
        while (l1 || l2 || carry) {
            if (l1) a = l1->val;
            else    a = 0;
            if (l2) b = l2->val;
            else    b = 0;
            c = (a + b + carry) % 10;//直接逆序計算序列,存入取余之後iude
            append(pl3, c); //將c存入鏈表中
            pl3 = pl3->next;
            carry = (a + b + carry) / 10;//將進位存在carry中
            if (l1) l1 = l1->next;
            if (l2) l2 = l2->next;

        }
        ListNode *ret = l3->next;
        delete l3;
        return ret;
    }
};