目录

LeetCode2 两数相加

LeetCode445 两数相加II

---

LeetCode2 两数相加

 

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {ListNode *dummy=new ListNode(0); //初始化, dummy->next被初始化为nullptrListNode* cur=dummy;ListNode* p1=l1;ListNode* p2=l2;int carry=0; //进位while(p1||p2||carry){ // 有一个不是空节点，或者还有进位，就继续迭代int sum=carry+(p1==nullptr? 0:p1->val)+(p2==nullptr? 0:p2->val);carry=sum/10;cur->next=new ListNode(sum%10);cur=cur->next;if(p1) p1=p1->next;if(p2) p2=p2->next;}return dummy->next;}
};

时间复杂度：O(n)

空间复杂度：O(1) （返回值不计入）

LeetCode445 两数相加II

 先将两个链表反转再相加。

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/class Solution {
public:ListNode* reverse(ListNode* L){ListNode* cur=L;ListNode* pre=nullptr;ListNode* nex;while(cur){nex=cur->next;cur->next=pre;pre=cur;cur=nex;}return pre;}ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {ListNode* p1=reverse(l1);ListNode* p2=reverse(l2);int carry=0;ListNode* dummy=new ListNode(0);ListNode* cur=dummy;while(p1||p2||carry){int sum=carry+(p1==nullptr? 0:p1->val)+(p2==nullptr? 0:p2->val);carry=sum/10;cur->next=new ListNode(sum%10);cur=cur->next;if(p1) p1=p1->next;if(p2) p2=p2->next;}return reverse(dummy->next);}
};

时间复杂度：O(n)

空间复杂度：O(1) （返回值不计入）