[LeetCode-2] Add Two Numbers（链表数据之和）

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; }