題目:給出兩個 非空 的鏈表用來表示兩個非負的整數(shù)箕昭。其中,它們各自的位數(shù)是按照 逆序 的方式存儲的解阅,并且它們的每個節(jié)點只能存儲 一位 數(shù)字落竹。
如果,我們將這兩個數(shù)相加起來货抄,則會返回一個新的鏈表來表示它們的和述召。
您可以假設除了數(shù)字 0 之外,這兩個數(shù)都不會以 0 開頭蟹地。
示例:
輸入:(2 -> 4 -> 3) + (5 -> 6 -> 4)
輸出:7 -> 0 -> 8
原因:342 + 465 = 807
Related Topics: 鏈表 數(shù)學
思路:既然要求是非空鏈表积暖,那我們首先要創(chuàng)建一個鏈表ListNode;兩個數(shù)相加锈津,那其實就是寫一個遞歸呀酸,遞歸最麻煩的是確定結束條件,和下一次遞歸的參數(shù)
結束條件:節(jié)點1+節(jié)點2=0琼梆;說明兩個節(jié)點都是空節(jié)點性誉;
節(jié)點1和節(jié)點2的下一節(jié)點都為null
1、構建鏈表節(jié)點
public class ListNode<T> {
//節(jié)點包含的值
private T value;
//下一個節(jié)點指向
private ListNode<T> next;
//初始化一個節(jié)點
public ListNode(T value) {
this.value = value;
}
//給節(jié)點添加下一個節(jié)點
public void add(ListNode<T> newNode){
if(this.next == null){
this.next = newNode;
}else {
this.next.add(newNode);
}
}
public static void main(String[] args) {
ListNode listNode = new ListNode(0);
listNode.add(new ListNode(0));
listNode.add(new ListNode(0));
}
}
2茎杂、確定遞歸
2.1 實現(xiàn)一
把運算的值存儲到一個空的節(jié)點l3中
public static void main(String[] args) {
ListNode<Integer> l1 = new ListNode<Integer>(2);
l1.add(new ListNode(4));
l1.add(new ListNode(3));
ListNode<Integer> l2 = new ListNode<Integer>(5);
l2.add(new ListNode(6));
l2.add(new ListNode(4));
ListNode l3 = new ListNode(0);
addTwoNumbers1(l1, l2, l3);
System.out.println("===");
}
private static ListNode<Integer> addTwoNumbers1(ListNode<Integer> l1, ListNode<Integer> l2, ListNode<Integer> l3) {
Integer v1 = l1==null?0:l1.getValue();
Integer v2 = l2==null?0:l2.getValue();
Integer v3 = l3==null?0:l3.getValue();
int temp = v1 + v2 + v3;
if(temp >= 10){
l3.setValue(temp % 10);
l3.add(new ListNode(temp /10));
}else if(temp < 10) {
l3.setValue(temp);
if((null == l1||null==l1.getNext()) && (null ==l2|| null==l2.getNext())){
return l3;
}
l3.add(new ListNode(0));
}if (temp == 0){
return l3;
}
return addTwoNumbers1(l1==null?null:l1.getNext(),l2==null?null:l2.getNext(),l3.getNext());
}
}
2.2 實現(xiàn)二
把運算的值存儲到已有的節(jié)點l1中
public class addTwoNumbers {
public static void main(String[] args) {
ListNode<Integer> l1 = new ListNode<Integer>(2);
l1.add(new ListNode(4));
l1.add(new ListNode(3));
ListNode<Integer> l2 = new ListNode<Integer>(5);
l2.add(new ListNode(6));
l2.add(new ListNode(4));
addTwoNumbers2(l1, l2);
System.out.println("===");
}
private static ListNode<Integer> addTwoNumbers2(ListNode<Integer> l1, ListNode<Integer> l2) {
//先判斷當前節(jié)點是否為null
Integer v1 = l1==null?0:l1.getValue();
Integer v2 = l2==null?0:l2.getValue();
int temp = v1 + v2 ;
//累加大于10的話错览,需要進位
if(temp >= 10){
l1.setValue(temp%10);
//累加運算的結果是要更新在l1的相應位置,所以進位需要判斷next是否為null
ListNode<Integer> next = l1.getNext();
if(null == next){
l1.add(new ListNode<>(1));
}else {
next.setValue(next.getValue() + 1);
}
}if (temp == 0){
//等于0的話煌往,說明當前節(jié)點都是null倾哺,退出遞歸
return l1;
} else if(temp < 10) {
//小于10的話,不需要進位
l1.setValue(temp);
//但是需要判斷當前節(jié)點的下一節(jié)點是否為null刽脖,如果是退出遞歸
if((null == l1||null==l1.getNext()) && (null ==l2|| null==l2.getNext())){
return l1;
}
//累加運算的結果是要更新在l1的相應位置羞海,所以需要判斷l(xiāng)1.next是否為null
//如果是的話,需要先添加一個空節(jié)點曲管,讓其存儲下一輪遞歸的值
if(null == l1.getNext()) {
l1.add(new ListNode(0));
}
}
return addTwoNumbers2(l1==null?null:l1.getNext(),l2==null?null:l2.getNext());
}
}