引言
题目链接:https://leetcode.com/problems/add-two-numbers/description/
题目大意
给出两个的倒序的链表,链表每个节点的值为非负个位数,链表反续串起来是一个数字,按照加法规则将两个链表相加并返回一个倒序链表,链表每个节点的数字对应计算结果的每一位。
例:
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.
Hint: You may assume the two numbers do not contain any leading zero, except the number 0 itself.
(不含前导零,数字本身可以为零)
题解
一句话题解:倒序链接正好由低位到高位表示了数字的每一位,直接取节点数据相加插入新链表节点即可(注意进位问题)
复杂度 O(n)
AC代码
c++版本
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
class Solution { public: ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) { ListNode *rList = NULL; ListNode *curNode; // 考虑进位 int carry = 0; while (NULL != l1 || NULL != l2) { int var1 = (NULL != l1) ? l1->val : 0; int var2 = (NULL != l2) ? l2->val : 0; if (NULL == rList) { rList = new ListNode((var1 + var2 + carry) % 10); curNode = rList; } else { curNode->next = new ListNode((var1 + var2 + carry) % 10); curNode = curNode->next; } l1 = (NULL == l1) ? l1 : l1->next; l2 = (NULL == l2) ? l2 : l2->next; carry = (var1 + var2 + carry) / 10; } if (carry > 0) { curNode->next = new ListNode(carry); } return rList; } }; |
go版本(感觉写的好挫,一点都不优雅 :[笑哭]:)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode { var rList, curNode *ListNode var carry, var1, var2 int for nil != l1 || nil != l2 { if nil != l1 { var1 = l1.Val l1 = l1.Next } else { var1 = 0 } if nil != l2 { var2 = l2.Val l2 = l2.Next } else { var2 = 0 } if nil == rList { rList = &ListNode{(var1 + var2 + carry) % 10, nil} curNode = rList } else { curNode.Next = &ListNode{(var1 + var2 + carry) % 10, nil} curNode = curNode.Next } carry = (var1 + var2 + carry) / 10 } if carry > 0 { curNode.Next = &ListNode{carry, nil} } return rList } |