转载

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

正文到此结束