[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 link
·
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;
}
开放原子开发者工作坊旨在鼓励更多人参与开源活动,与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动,如meetup、训练营等,主打技术交流,干货满满,真诚地邀请各位开发者共同参与!
更多推荐
已为社区贡献1条内容
所有评论(0)