2019/03/31
一开始的想法是简单的把这两个数表示出来然后相加，再将各个位填入链表中，代码如下：
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { //得到链表L1代表的整数 long long multiply = 1; long long addL = 0; //L1链表所表示的整数 ListNode* pWorkNode = l1; while (pWorkNode) { addL += multiply * pWorkNode->val; //将各位数组成和整数 multiply *= 10; pWorkNode = pWorkNode->next; } //将链表L2所代表整数与L1中的相加 multiply = 1; pWorkNode = l2; while (pWorkNode) { addL += multiply * pWorkNode->val; multiply *= 10; pWorkNode = pWorkNode->next; } //所得整数按位数存入链表 multiply = 10; long result = addL; ListNode* L3 = nullptr; ListNode* pTialNode = nullptr; while(result) { ListNode* pNewNode = new ListNode(result % multiply); result /= multiply; if (!L3) //创建第一个结点 { L3 = pNewNode; L3->next = nullptr; pTialNode = pNewNode; } else { pTialNode->next = pNewNode; pTialNode = pNewNode; } pTialNode->next = nullptr; } return L3; }
执行结果是失败的，当有链表较长时，基本数据类型会溢出。之所以会这样想，感觉自己思考的时候没有条理性，不清晰。下次分析的时候一定要吸取教训，这样做是没什么效果的。
方法二：
时间复杂度O(n)，空间复杂度O(n)
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { ListNode* pWorkNodeL1 = l1; ListNode* pWorkNodeL2 = l2; int valL1, valL2, num, carry = 0; //从左到右分别是L1/L2对应位中的数值、L3当前结点的数值、进位 ListNode* L3 = new ListNode(0); //创建头结点 ListNode* pTialNode = L3; while (pWorkNodeL1 || pWorkNodeL2 || carry) //如果两个链表都到末尾则结束 { if (!pWorkNodeL1) valL1 = 0; else { valL1 = pWorkNodeL1->val; pWorkNodeL1 = pWorkNodeL1->next; } if (!pWorkNodeL2) valL2 = 0; else { valL2 = pWorkNodeL2->val; pWorkNodeL2 = pWorkNodeL2->next; } num = (valL1 + valL2 + carry) % 10; ListNode* pNewNode = new ListNode(num); carry = (valL1 + valL2 + carry) / 10; pTialNode->next = pNewNode; pTialNode = pNewNode; pTialNode->next = nullptr; } return L3->next; }
执行效果如下：
原文：https://www.cnblogs.com/zpchya/p/10633975.html