我的思路:链表高精度加法
时间复杂度 $O(n)$ 空间复杂度 $O(1)$
l r标记哪个链表长
ll rr标记链表尾,以防t一直进位
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
int l = 0, r = 0;
ListNode ll = l1, rr = l2;
ListNode head1 = l1, head2 = l2;
int t = 0;
while(head1 != null || head2 != null) {
if(head1 != null) {
t += head1.val;
l ++ ;
ll = head1;
head1 = head1.next;
}
if(head2 != null) {
t += head2.val;
r ++ ;
rr = head2;
head2 = head2.next;
}
if(ll != null) ll.val = t % 10;
if(rr != null) rr.val = t % 10;
t /= 10;
}
if(t != 0) {
if(l > r) ll.next = new ListNode(t);
else rr.next = new ListNode(t);
}
return l > r ? l1 : l2;
}
}
优化后代码
并不需要l、r、head1、head2,只需要用一个头指针dummy方便返回 和 一个前指针pre记录当前不为空的点在哪里
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(-1);
ListNode pre = dummy;
int t = 0;
while(l1 != null || l2 != null) {
if(l1 != null) {
t += l1.val;
pre.next = l1;
l1 = l1.next;
}
if(l2 != null) {
t += l2.val;
pre.next = l2;
l2 = l2.next;
}
pre = pre.next;
pre.val = t % 10;
t /= 10;
if((l1 == null && l2 == null) && t != 0) pre.next = new ListNode(t);
}
return dummy.next;
}
}
简约代码 + 空间复杂度上升至O(n)
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode yummy = new ListNode(-1);
ListNode pre = yummy;
int t = 0;
while(l1 != null || l2 != null || t != 0) {
if(l1 != null) {
t += l1.val;
l1 = l1.next;
}
if(l2 != null) {
t += l2.val;
l2 = l2.next;
}
pre = pre.next = new ListNode(t % 10);
t /= 10;
}
return yummy.next;
}
}