一、原题
You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
二、中文
有两个单链表,代表两个非负数,每一个节点代表一个数位,数字是反向存储的,即第一个结点表示最低位,最后一个结点表示最高位。求两个数的相加和,并且以链表形式返回。
三、举例
输入链表 1->2->3->4 和链表 1->8->3->4 最后得到链表 2->0->7->8
四、思路
(1)构建两链表从最左边开始相加,其结果存入另外一个链表
(2)当相加之和小于10时,不产生进位,当大于等于10的时候,产生进位
(3)这里要注意一种情况,就是当最后的一对结点相加之和大于等于10的时候也要产生进位,这是需要创建一个新的结点
五、程序
package LeetCode;
public class Leetcode002 {
public static void main(String args[]){
//测试程序,链表1:1->8->3->6,链表2:1->2->3->4
ListNode node1 = new ListNode();
node1.value = https://www.it610.com/article/1;
node1.next = new ListNode();
node1.next.value = 8;
node1.next.next = new ListNode();
node1.next.next.value = 3;
node1.next.next.next = new ListNode();
node1.next.next.next.value = 6;
ListNode node2 = new ListNode();
node2.value = 1;
node2.next = new ListNode();
node2.next.value = 2;
node2.next.next = new ListNode();
node2.next.next.value = 3;
node2.next.next.next = new ListNode();
node2.next.next.next.value = 4;
ListNode node3 = new ListNode();
node3 = addTwoLists(node1, node2);
//打印我们返回的链表结果
while(node3 != null){
System.out.print(node3);
node3 = node3.next;
} }
//创建一个链表的类
public static class ListNode{
int value;
ListNode next;
public ListNode(){}public String toString(){
return value+"->";
} }
public static ListNode addTwoLists(ListNode head1, ListNode head2){
if(head1 == null || head2 == null){
return null;
}ListNode head3 = new ListNode();
// 保存头结点,最后返回的时候用
ListNode storeNode = head3;
int flag = 0;
int sum = 0;
while(head1 != null && head2 != null){
sum = head1.value + head2.value + flag;
flag = 0;
if(sum < 10){
head3.value = https://www.it610.com/article/sum;
}
else if(sum>= 10){
flag = 1;
head3.value = https://www.it610.com/article/sum - 10;
}
head1 = head1.next;
head2 = head2.next;
//创建一个新的结点,前提是不是到达两个链表最后的元素时
if(head1 != null && head2 != null){
ListNode newnode = new ListNode();
head3.next = newnode;
head3 = head3.next;
}
}// 如果有一个为空的情况下执行
if(head1 == null){
head3.next = head2;
}
if(head2 == null){
head3.next = head1;
}// 也就是说最后一位相加还有进位,要创建一个新的结点
if(flag == 1){
ListNode lastnode = new ListNode();
lastnode.value = 1;
head3.next = lastnode;
}
return storeNode;
}
}
-------------output---------------
2->0->7->0->1->
【Leetcode002--单链表两数相加】
推荐阅读
- 【leetcode】28. 实现strStr() 【字符串】
- 【leetcode】|leetcode 35. Search Insert Position 搜索插入位置 python 简单而高效的方法、二分查找
- 【leetcode】|leetcode 28 implement strStr() (实现strStr()) python3 多种思路(熟悉string的内建函数,str的切片操作)