题目
给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例
输入： (2 -> 4 -> 3) + (5 -> 6 -> 4)
输出： 7 -> 0 -> 8
原因： 342 + 465 = 807
解题思路
同时遍历2个链表，时间复杂度 O(max(x, y))，耗时2ms，
进位标记直接写入结果链表的下标，无需额外变量，节省空间。
整体代码简洁易懂。
代码
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
35
36
37
38
|
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode mov_x = l1;
ListNode mov_y = l2;
ListNode ret = new ListNode(0);
ListNode mov_ret = ret;
while(mov_x != null || mov_y != null){
int x = mov_x!=null ? mov_x.val : 0; // 补0
int y = mov_y!=null ? mov_y.val : 0; // 补0
mov_ret.val += x+y;
if(mov_ret.val > 9){
mov_ret.val -= 10;
// 进位标记写入ret.next
mov_ret.next = new ListNode(1);
} else if ((mov_x!=null && mov_x.next !=null) || (mov_y != null && mov_y.next != null)) {
// 如果链表下标还有值, 则new一个ret.next
mov_ret.next = new ListNode(0);
}
mov_x = mov_x!=null ? mov_x.next : null;
mov_y = mov_y!=null ? mov_y.next : null;
mov_ret = mov_ret.next;
}
return ret;
}
}
|
