[LeetCode-2] Add Two Numbers（鏈表數據之和），leetcode-2numbers

[LeetCode-2] Add Two Numbers（鏈表數據之和），leetcode-2numbers

You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

【分析】思路非常簡單，利用兩個指針分別遍歷兩個鏈表，並且用一個變量表示是否有進位。某個鏈表遍歷結束之後再將另一個鏈表連接在結果鏈表之後即可，若最後有進位需要添加一位。

struct ListNode* addTwoNumbers(struct ListNode* FirstLists, 
                                    struct ListNode* SecondLists)
{
    /*1.異常處理*/
    if(!FirstLists && !SecondLists)
        return NULL;
    
    struct ListNode *FirstListsTemp = FirstLists;
    struct ListNode *SecondListsTemp = SecondLists;
    struct ListNode *head = NULL;
    struct ListNode *headTemp = NULL;
    
    int TwoNumbersSum = 0;
    int TwoNumbersGain = 0; 
    
    while(FirstLists && SecondLists) {
        TwoNumbersSum = FirstLists->val + SecondLists->val + TwoNumbersGain;
        TwoNumbersGain = TwoNumbersSum/10;
        TwoNumbersSum = TwoNumbersSum%10;
        /*2.保存頭結點*/
        if (NULL == head) {
            head = (struct ListNode *)malloc(sizeof(struct ListNode));
            head->val = TwoNumbersSum;
            headTemp = head;
            headTemp->next = NULL;
        }
        else {
            headTemp->next = (struct ListNode *)malloc(sizeof(struct ListNode));
            headTemp = headTemp->next;
            headTemp->val = TwoNumbersSum;
            headTemp->next = NULL;
        }
        FirstLists = FirstLists->next;
        SecondLists = SecondLists->next;
    }
    
    while(FirstLists) {
        TwoNumbersSum = FirstLists->val + TwoNumbersGain;
        TwoNumbersGain = TwoNumbersSum/10;
        TwoNumbersSum = TwoNumbersSum%10;
        
        if (NULL == head) {
            head = (struct ListNode *)malloc(sizeof(struct ListNode));
            head->val = TwoNumbersSum;
            headTemp = head;
            headTemp->next = NULL;
        }
        else {
            headTemp->next = (struct ListNode *)malloc(sizeof(struct ListNode));
            headTemp = headTemp->next;
            headTemp->val = TwoNumbersSum;
            headTemp->next = NULL;
        }    
        FirstLists = FirstLists->next;
    }

    while(SecondLists) {
        TwoNumbersSum = SecondLists->val + TwoNumbersGain;
        TwoNumbersGain = TwoNumbersSum/10;
        TwoNumbersSum =   TwoNumbersSum%10;
        
        if (NULL == head) {
            head = (struct ListNode *)malloc(sizeof(struct ListNode));
            head->val = TwoNumbersSum;
            headTemp = head;
            headTemp->next = NULL;
        }
        else {
            headTemp->next = (struct ListNode *)malloc(sizeof(struct ListNode));
            headTemp = headTemp->next;
            headTemp->val = TwoNumbersSum;
            headTemp->next = NULL;
        }
        SecondLists = SecondLists->next;
    }

    if(TwoNumbersGain) {
        headTemp->next = (struct ListNode *)malloc(sizeof(struct ListNode));
        headTemp = headTemp->next;
        headTemp->val = TwoNumbersGain%10;
        headTemp->next = NULL;
    }

    return head;
}

完整代碼如下：

// addTwoNumbers.cpp : 定義控制台應用程序的入口點。
//

#include "stdafx.h"

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/**
 * Definition for singly-linked list.
 **/
 
 struct ListNode {
      int val;
      struct ListNode *next;
 };
 

 struct ListNode* CreatLink(int aData[],int len)
 {
     if(!aData)
         return NULL;
     struct ListNode *head = NULL;
     struct ListNode *p = NULL;
     struct ListNode *Link= NULL;
     /*第一個節點*/
     head = (struct ListNode *)malloc(sizeof(struct ListNode));
     head->val = aData[0];
     head->next = NULL;
    // aData ++;
     Link = head; /*保存頭結點*/
     int i = 1;

     while(i < len) {
         p = (struct ListNode *)malloc(sizeof(struct ListNode));
         p->val = aData[i];
         head->next = p;
         head = p;
         i ++;
     }

     head->next = NULL;
     return Link;
 }

 void printLink(struct ListNode *head)
 {
     while(head) {
         printf("%d",head->val);
         head = head->next;
     }
     printf("\n");
 }

struct ListNode* addTwoNumbers(struct ListNode* FirstLists, 
                                    struct ListNode* SecondLists)
{
    /*1.異常處理*/
    if(!FirstLists && !SecondLists)
        return NULL;
    
    struct ListNode *FirstListsTemp = FirstLists;
    struct ListNode *SecondListsTemp = SecondLists;
    struct ListNode *head = NULL;
    struct ListNode *headTemp = NULL;
    
    int TwoNumbersSum = 0;
    int TwoNumbersGain = 0; 
    
    while(FirstLists && SecondLists) {
        TwoNumbersSum = FirstLists->val + SecondLists->val + TwoNumbersGain;
        TwoNumbersGain = TwoNumbersSum/10;
        TwoNumbersSum = TwoNumbersSum%10;
        /*2.保存頭結點*/
        if (NULL == head) {
            head = (struct ListNode *)malloc(sizeof(struct ListNode));
            head->val = TwoNumbersSum;
            headTemp = head;
            headTemp->next = NULL;
        }
        else {
            headTemp->next = (struct ListNode *)malloc(sizeof(struct ListNode));
            headTemp = headTemp->next;
            headTemp->val = TwoNumbersSum;
            headTemp->next = NULL;
        }
        FirstLists = FirstLists->next;
        SecondLists = SecondLists->next;
    }
    
    while(FirstLists) {
        TwoNumbersSum = FirstLists->val + TwoNumbersGain;
        TwoNumbersGain = TwoNumbersSum/10;
        TwoNumbersSum = TwoNumbersSum%10;
        
        if (NULL == head) {
            head = (struct ListNode *)malloc(sizeof(struct ListNode));
            head->val = TwoNumbersSum;
            headTemp = head;
            headTemp->next = NULL;
        }
        else {
            headTemp->next = (struct ListNode *)malloc(sizeof(struct ListNode));
            headTemp = headTemp->next;
            headTemp->val = TwoNumbersSum;
            headTemp->next = NULL;
        }    
        FirstLists = FirstLists->next;
    }

    while(SecondLists) {
        TwoNumbersSum = SecondLists->val + TwoNumbersGain;
        TwoNumbersGain = TwoNumbersSum/10;
        TwoNumbersSum =   TwoNumbersSum%10;
        
        if (NULL == head) {
            head = (struct ListNode *)malloc(sizeof(struct ListNode));
            head->val = TwoNumbersSum;
            headTemp = head;
            headTemp->next = NULL;
        }
        else {
            headTemp->next = (struct ListNode *)malloc(sizeof(struct ListNode));
            headTemp = headTemp->next;
            headTemp->val = TwoNumbersSum;
            headTemp->next = NULL;
        }
        SecondLists = SecondLists->next;
    }

    if(TwoNumbersGain) {
        headTemp->next = (struct ListNode *)malloc(sizeof(struct ListNode));
        headTemp = headTemp->next;
        headTemp->val = TwoNumbersGain%10;
        headTemp->next = NULL;
    }

    return head;
}

int main()
{
    int a[3] = {2,4,3};
    int b[3] = {5,6,4};
    struct ListNode *head1 = NULL;
    struct ListNode *head2 = NULL;
    struct ListNode *head3 = NULL;
    head1 = CreatLink(a,3);
    printLink(head1);

    head2 = CreatLink(b,3);
    printLink(head2);

    head3 = addTwoNumbers(head1,head2);
    printLink(head3);
    /*To Do:釋放內存*/
    getchar();
    return 0;

}