原题链接:https://www.nowcoder.com/practice/c56f6c70fb3f4849bc56e33ff2a50b6b
假设链表中每一个节点的值都在 0 - 9 之间,那么链表整体就可以代表一个整数。 给定两个这种链表,请生成代表两个整数相加值的结果链表。
数据范围:0 \le n,m \le 10000000≤n,m≤1000000,链表任意值 0 \le val \le 90≤val≤9
要求:空间复杂度 O(n)O(n),时间复杂度 O(n)O(n)例如:链表 1 为 9->3->7,链表 2 为 6->3,最后生成新的结果链表为 1->0->0->0。
一开始没看到数据要求,试着用转成数字直接相加,结果当然是不对的,因为题目给的位数非常大,因此必须一位一位的处理。
我选择了先将两个链表反转再进行相加,要记得处理进位的情况即可。
class Solution {
public:
// 反转链表
ListNode* reverse(ListNode* head) {
ListNode* pre = nullptr;
ListNode* cur = head;
while (cur) {
ListNode* next = cur->next;
cur->next = pre;
pre = cur;
cur = next;
}
return pre;
}
/**
*
* @param head1 ListNode类
* @param head2 ListNode类
* @return ListNode类
*/
ListNode* addInList(ListNode* head1, ListNode* head2) {
// write code here
head1 = reverse(head1);
head2 = reverse(head2);
ListNode* cur = new ListNode(-1);
ListNode* pre = nullptr;
bool ex = false;// 标记进位
while (head1 || head2) {
int sum = 0;
if (head1) {
sum += head1->val;
head1 = head1->next;
}
if (head2) {
sum += head2->val;
head2 = head2->next;
}
cur = new ListNode((sum + ex) % 10);
cur->next = pre;
pre = cur;
ex = (sum + ex) / 10;
}
return cur;
}
};
本文作者:TTQ
本文链接:https://blog.ponder.fun/archives/141.html
最后修改时间:2022-04-21 22:03:46
本站未注明转载的文章均为原创,并采用 CC BY-NC-SA 4.0 授权协议,转载请注明来源,谢谢!