LeetCode 2 Add Two Sum 解题报告
LeetCode第二题 Add Two Sum 首先我们看题目要求：
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
题目分析
这道题目是一道基础的链表题，给定两个非负数，它们是按照逆序存储的，每个节点值保留一个数值，要求输出这两个数之和，返回结果链表。本道题目主要是考察链表遍历的一些操作。
思路
1.首先用两个指针，分别同时遍历两个链表，按位相加，设置相应进位标志。
2.当两个链表长度不一致时，结束按位相加的遍历之后，将剩余链接接上
3.需要注意连续进位。
以下给出完整的测试代码，在这里为了操作方便，在遍历时统一把数据放到了list的容器中，主要是担心，对于链接，连续进位时直接用指针new出错，直接将每一位Push到list中，最后直接通过list构造出一个ListNode的链表
#include<iostream>
#include<list>
using namespace std;
struct ListNode
{
int val;
ListNode * next;
ListNode(int x):val(x),next(NULL){}
};
ListNode * createListNode( int * arr, int num)
{
int i = 0;
ListNode * head = new ListNode(arr[0]);//head pointer
ListNode * p1 = head;
ListNode * p2 = head;
if(num == 1)
{
head->next = NULL;
return head;
}
else
{
for(i = 1; i < num; i++)
{
p1 = new ListNode(arr[i]);
p2->next = p1;
p2 = p1;
}
p1->next = NULL;
}
return head;
}
class Solution
{
public:
ListNode * createListNode2( list<int> iList)//
{
int num = iList.size();
list<int>::iterator it = iList.begin();
ListNode * head = new ListNode(*it);//head pointer
ListNode * p1 = head;
ListNode * p2 = head;
it++;
if(num == 1)
{
head->next = NULL;
return head;
}
else
{
for(; it != iList.end(); it++)
{
p1 = new ListNode(*it);
p2->next = p1;
p2 = p1;
}
p1->next = NULL;
}
return head;
}
ListNode * addTwoNumbers (ListNode * ln1,ListNode * ln2)
{
list<int> result;
ListNode * p;
ListNode * p1 = ln1;
ListNode * p2 = ln2;
int carryFlag = 0;
int curNum = 0;
while(p1 != NULL && p2 != NULL)
{
curNum = (p1->val + p2->val + carryFlag)%10;
if((p1->val + p2->val + carryFlag) >= 10)
carryFlag = 1;
else
carryFlag = 0;
result.push_back(curNum);
p1 = p1->next;
p2 = p2->next;
}
if(p1 == NULL && p2 == NULL)
{
if (carryFlag == 1)
result.push_back(carryFlag);
}
else if(p1 != NULL && p2 == NULL )
{
while(p1 != NULL)
{
curNum = (p1->val+carryFlag) %10;
if(p1->val + carryFlag >= 10)
carryFlag = 1;
else
carryFlag = 0;
result.push_back(curNum);
p1 = p1->next;
}
if(carryFlag ==1 )
result.push_back(carryFlag);
}
else if(p1 == NULL && p2 != NULL)
{
while(p2 != NULL)
{
curNum = (p2->val+carryFlag) %10;
if(p2->val + carryFlag >= 10)
carryFlag = 1;
else
carryFlag = 0;
result.push_back(curNum);
p2 = p2->next;
}
if(carryFlag == 1 )
result.push_back(carryFlag);
}
list<int>::iterator it = result.begin();
for(;it != result.end(); it++)
cout<<*it;
return createListNode2(result);
}
};
int main ()
{
int arr1[] = {1};
int arr2[] = {9,9};
Solution s1;
ListNode *l1 = createListNode(arr1,1);
ListNode *l2 = createListNode(arr2,2);
s1.addTwoNumbers(l1,l2);
return 0;
return 0;
}