Leetcode解题笔记之（二）——Add Two Numbers [Medium]

解题思路

这道题就是将两个数用链表表示然后将这两个数相加，方法很简单粗暴，直接加就可以了。但是这里有一点要注意，就是这两个数的位数可能不一样，即这两个链表的长度可能不一样，所以我们需要做好创建新节点的准备。

代码

ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { ListNode* iter1 = l1; ListNode* iter2 = l2; ListNode *temp = NULL, *result = NULL; int v1, v2; int carryBit = 0; int tempVal = 0; while (iter1 != NULL || iter2 != NULL) { v1 = iter1 ? iter1->val : 0; v2 = iter2 ? iter2->val : 0; int sum = v1 + v2 + carryBit; tempVal = sum % 10; carryBit = sum / 10; // 判断是否是第一个数据 if (result == NULL) { result = temp = new ListNode(tempVal); } else { temp->next = new ListNode(tempVal); temp = temp->next; } iter1 = iter1 ? iter1->next : iter1; iter2 = iter2 ? iter2->next : iter2; } //最后一个是否存在进位判断 if (carryBit != 0) { temp->next = new ListNode(carryBit); } return result; }

复杂度

O(n)： 简单地遍历两条链