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

62 阅读 0 评论 41 点赞

我是靠谱客的博主踏实毛豆，最近开发中收集的这篇文章主要介绍LeetCode2. 两数相加（链表 + java），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

两数相加

1. 题目描述：

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

示例：

输入：(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;
}
```
用两个指针（引用）p1和p2
- p1用于循环创建节点 p1.next = new ListNode(0); p1 = p1.next ;
```
	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;
}
```

java代码：

/**
* 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;
}
}