leecode 第二题
给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例：
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807
题解：：遍历两个列表和两个列表的一个接一个节点并添加值。如果总和大于10，使进位为1并取和的余数。如果一个列表比另一个列表具有更多元素，则设该列表的剩余值为0。
步骤：
从头到尾遍历两个链接列表。
将两个数字分别从各自的链接列表中添加。
如果列表之一已到达末尾，则将0用作其数字。
继续进行直到两个列表都结束。
如果两个数字的总和大于9，则将进位设置为，将当前数字设置为总和％10
核心代码
class Solution {
/*
* 添加两个链表的内容，并返回结果链表的头节点
*/
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
// res 作为结果列表的头节点
ListNode res = null;
ListNode pre = null;
ListNode temp = null;
int carry =0;//进位
int sum;
//当两个列表都存在时
while(l1 != null || l2 != null){
int x = l1 == null ? 0:l1.val;
int y = l2 == null ? 0:l2.val;
sum = x + y +carry;
//为下一次计算更新进位
carry= sum > 9 ? 1:0;
//如果sum大于10，则更新sum
sum=sum%10;
//创建一个以sum作为数据的新节点
temp = new ListNode(sum);
//如果这是第一个节点，那么设置他为结果列表的头
if(res == null){
res = temp;
}
//如果它不是第一个节点，将其连到其他节点
else{
pre.next = temp;
}
//设置 temp 为下一个节点
pre = temp;
//移动第一和第二指针
//到下一个节点
if(l1 != null){
l1 =l1.next;
}
if(l2 != null){
l2=l2.next;
}
}
//如果最后产生进位，则创建一个新节点存放进位
if(carry>0){
temp.next = new ListNode(carry);
}
//返回结果列表的头
return res;
}
}
自己在 IDEA中实现：
链表的创建：
///用 LinkedList表示链表
static Node head1,head2;
static class Node {
int data;
Node next;
Node(int d)
{
data = d;
next =null;
}
主函数：
public static void main(String[] args)
{
LinkedList list = new LinkedList();
// 创建第一个链表
list.head1 = new Node(7);
list.head1.next = new Node(5);
list.head1.next.next = new Node(9);
list.head1.next.next.next = new Node(4);
list.head1.next.next.next.next = new Node(6);
System.out.print("第1个链表 ");
list.printList(head1);
// 创建第二个链表
list.head2 = new Node(8);mbn
list.head2.next = new Node(4);
System.out.print("第2个链表");
list.printList(head2);
// 相加并显示结果
Node rs = list.addTwoLists(head1, head2);
System.out.print("结果链表：");
list.printList(rs);
}
网友评论