两数相乘

两数相乘

给出两个链表形式表示的数字,写一个函数得到这两个链表相乘乘积。

样例

样例 1:

输入：9->4->6->null,8->4->null
输出：79464
解释：946*84=79464

样例 2:

输入：3->2->1->null,1->2->null
输出：3852
解释：321*12=3852

 

/*** Definition of singly-linked-list:* class ListNode {* public:*     int val;*     ListNode *next;*     ListNode(int val) {*        this->val = val;*        this->next = NULL;*     }* }*/class Solution {
public:/*** @param l1: the first list* @param l2: the second list* @return: the product list of l1 and l2*/long long multiplyLists(ListNode * l1, ListNode * l2) {// write your code here string num1  = "";string num2  = ""; while(l1){char ch = l1->val + 48;num1 += ch;l1 = l1->next;}while(l2){char ch = l2->val + 48;num2 += ch;l2 = l2->next;}return stoll(multiply(num1, num2));}string multiply(string num1, string num2) {int l1 = num1.length();int l2 = num2.length();vector<int> ans(l1 + l2 + 1, 0);for (int i = 0; i < l1; i++) {for (int j = 0; j < l2; j++) {ans[i + j] += (num1[l1 - 1 - i] - '0') * (num2[l2 - 1 - j] - '0');}}for(int i = 0; i < l1 + l2; i++) {ans[i + 1] += ans[i] / 10;ans[i] %= 10;}int i = l1 + l2;while (ans[i] == 0 && i >= 1) {i--;}string str;while (i >= 0) {str += (char)(ans[i--] + '0');}return str;}
};