两个链表相加求和算法

你有两个用链表代表的整数，其中每个节点包含一个数字。数字存储按照在原来整数中相反的顺序，使得第一个数字位于链表的开头。写出一个函数将两个整数相加，返回和。
若链表存储是从高位开始存储，则将链表先反转再相加。反转链表实现

#include #include #includestruct Node { int data; Node* next; Node() : data(0), next(NULL) {} }; Node* createList(int* list, int size) { if (0 == size) { return NULL; } Node* head = NULL, *p = NULL; head = p = new Node(); p->data = https://www.it610.com/article/list[0]; p->next = NULL; for (int i = 1; i < size; i++) { Node* cur = new Node(); cur->data = https://www.it610.com/article/list[i]; cur->next = NULL; p->next = cur; p = cur; }return head; }void toString(Node* pList) { Node* p = pList; while (p) { std::cout << p->data << ","; p = p->next; } std::cout << std::endl; }std::string sumList(Node* pList1, Node* pList2) { int flag = 0; Node* p1 = pList1; Node* p2 = pList2; std::vector result; while (true) { int sum = 0; if (p1 != NULL) { sum += p1->data; p1 = p1->next; } if (p2 != NULL) { sum += p2->data; p2 = p2->next; } sum += flag; flag = sum / 10; result.push_back(sum % 10); if (p1 == NULL && p2 == NULL) { break; } } if (flag > 0) { result.push_back(flag); } std::ostringstream os; for (std::vector::reverse_iterator numIter = result.rbegin(); numIter != result.rend(); ++numIter) { os << *numIter; } return os.str(); }int main() { int list1[] = {1,3,9,8}; int list2[] = {2,5,7,4,2}; Node* pList1 = createList(list1, sizeof(list1)/sizeof(int)); Node* pList2 = createList(list2, sizeof(list2)/sizeof(int)); toString(pList1); toString(pList2); std::cout << sumList(pList1, pList2) << std::endl; return 0; }

【两个链表相加求和】