目录
牛客_NC40链表相加(二)_链表+高精度加法
题目解析
C++代码
Java代码
牛客_NC40链表相加(二)_链表+高精度加法
链表相加(二)_牛客题霸_牛客网
题目解析
模拟⾼精度加法的过程,只不过是在链表中模拟。
C++代码
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* ListNode(int x) : val(x), next(nullptr) {}
* };
*/
class Solution {public:/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* @param head1 ListNode类
* @param head2 ListNode类
* @return ListNode类
*/ListNode* addInList(ListNode* head1, ListNode* head2) {string s, t;while(head1){s += head1->val + '0';head1 = head1->next;}while(head2){t += head2->val + '0';head2 = head2->next;}string res = solve(s, t);// cout << res;if(res.size() == 0){return nullptr;}ListNode* cur;cur = new ListNode(res[0] - '0');ListNode* ret = cur;for(int i = 1; i < res.size(); ++i){ListNode* tmp = new ListNode(res[i] - '0');cur->next = tmp;cur = cur->next;}cur->next = nullptr;return ret;}string solve(string s, string t) {int end1 = s.size() - 1, end2 = t.size() - 1;string ret;int carry = 0;while(end1 >= 0 || end2 >= 0){int val1 = end1 >= 0 ? s[end1] - '0' : 0;int val2 = end2 >= 0 ? t[end2] - '0' : 0;ret += (val1 + val2 + carry) % 10 + '0';if(val1 + val2 + carry > 9){carry = 1;}else{carry = 0;}--end1;--end2;}if(carry){ret += '1';}reverse(ret.begin(), ret.end());return ret;}
};
Java代码
import java.util.*;
public class Solution
{// 逆序链表public ListNode reverse(ListNode head){ListNode newHead = new ListNode(0);ListNode cur = head;while(cur != null){ListNode next = cur.next;cur.next = newHead.next;newHead.next = cur;cur = next;}return newHead.next;}public ListNode addInList (ListNode head1, ListNode head2){// 1. 逆序head1 = reverse(head1);head2 = reverse(head2);// 2. ⾼精度加法ListNode cur1 = head1, cur2 = head2;int t = 0;ListNode ret = new ListNode(0), prev = ret;while(cur1 != null || cur2 != null || t != 0){if(cur1 != null){t += cur1.val;cur1 = cur1.next;}if(cur2 != null){t += cur2.val;cur2 = cur2.next;}prev = prev.next = new ListNode(t % 10);t /= 10;}return reverse(ret.next);}
}