题目地址https://leetcode.com/problems/add-two-numbers/给定两个链表从低位到高位表示一个十进制正整数没有开头0 00要求返回两个十进制数之和代表的链表。高精度加法的应用直接模拟手工加法。代码如下/** * 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) {} * }; */classSolution{public:ListNode*addTwoNumbers(ListNode*l1,ListNode*l2){ListNode*dummynewListNode(0),*prevdummy;intt0;while(l1||l2||t){if(l1)tl1-val,l1l1-next;if(l2)tl2-val,l2l2-next;prev-nextnewListNode(t%10);prevprev-next;t/10;}returndummy-next;}};时间复杂度O ( l 1 l 2 ) O(l_1l_2)O(l1​l2​)空间O ( max ⁡ { l 1 , l 2 } ) O(\max\{l_1,l_2\})O(max{l1​,l2​})。优化。可以直接复用输入。答案的长度一定不会超过两个链表节点总数所以复用绰绰有余。代码如下classSolution{public:ListNode*addTwoNumbers(ListNode*l1,ListNode*l2){ListNode dummy;autoprevdummy;autopl1l1,pl2l2;intt0;while(l1||l2||t){if(l1)tl1-val,l1l1-next;if(l2)tl2-val,l2l2-next;pl1?(prev-nextpl1,pl1pl1-next):(prev-nextpl2,pl2pl2-next);prevprev-next;prev-valt%10;t/10;}prev-nextnullptr;returndummy.next;}};时间复杂度不变空间O ( 1 ) O(1)O(1)。