LeetCode2. 两数相加（链表 + java）

两数相加

1. 题目描述：

​ 给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例：

1
2
3
4
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807

2. 题目分析：

​ 它们是按照逆序排的，也就是说是以个位开始排的，我们直接将个位对应个位相加，十位对应十位相加，以此类推，直到两个都为空；需要考虑的问题有

• 返回的那个链表，是新建一个，还是用已有的，这里为了简单[捂脸]，新建一个链表ret

• 进位carry的问题，由于是加法，carry的范围只能是0 ~ 18，需要考虑两种情况

  • carry < 10

  • carry >= 10

  • 复制代码if(carry >= 10) { p1.val = carry - 10; carry = 1; } else { p1.val = carry; carry = 0; }

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    
    if(carry >= 10)
    {
    p1.val = carry - 10;
    carry = 1;
    }
    else
    {
    p1.val = carry;
    carry = 0;
    }
    

• 用两个指针（引用）p1和p2

  • p1用于循环创建节点 p1.next = new ListNode(0); p1 = p1.next ;

    复制代码 p1.next = new ListNode(0); p1 = p1.next;

    1
    2
    3
    	p1.next = new ListNode(0);
    p1 = p1.next;
    

  • p2用于记录当前节点p1的上一个节点的位置。因为当创建一个新的节点时，接着发现l1和l2已经是null了，并且carry = 0，那么新创的这个节点就是多余了，那就把p2.next = null就可以抛弃这个新建的节点了；假如carry != 0；那么新创的这个节点还是有用的，令p1.val = carry; p1.next = null；

    复制代码if(carry != 0) { p1.val = carry; p1.next = null; } else { p2.next = null; }

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    
    if(carry != 0)
    {
    p1.val = carry;
    p1.next = null;
    }
    else
    {
    p2.next = null;
    }
    

java代码：

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
/**
* 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 ret = new ListNode(0);
ListNode p1 = ret;
ListNode p2 = ret;
int carry = 0;
while(l1 != null || l2 != null)
{
if(l1 != null)
{
carry += l1.val;
}
if(l2 != null)
{
carry += l2.val;
}
if(carry >= 10)
{
p1.val = carry - 10;
carry = 1;
}
else
{
p1.val = carry;
carry = 0;
}
p2 = p1;
p1.next = new ListNode(0);
p1 = p1.next;
if(l1 != null) l1 = l1.next;
if(l2 != null) l2 = l2.next;
}
if(carry != 0)
{
p1.val = carry;
p1.next = null;
}
else
{
p2.next = null;
}
return ret;
}
}

最后

以上就是踏实毛豆最近收集整理的关于LeetCode2. 两数相加（链表 + java）的全部内容，更多相关LeetCode2.内容请搜索靠谱客的其他文章。