LeetCode熱題2:Add Two Numbers

題目:給出兩個 非空 的鏈表用來表示兩個非負的整數(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());
    }
}

?著作權歸作者所有,轉載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末却邓,一起剝皮案震驚了整個濱河市,隨后出現(xiàn)的幾起案子院水,更是在濱河造成了極大的恐慌腊徙,老刑警劉巖,帶你破解...
    沈念sama閱讀 211,042評論 6 490
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件檬某,死亡現(xiàn)場離奇詭異撬腾,居然都是意外死亡,警方通過查閱死者的電腦和手機恢恼,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 89,996評論 2 384
  • 文/潘曉璐 我一進店門民傻,熙熙樓的掌柜王于貴愁眉苦臉地迎上來,“玉大人,你說我怎么就攤上這事饰潜〕踝梗” “怎么了?”我有些...
    開封第一講書人閱讀 156,674評論 0 345
  • 文/不壞的土叔 我叫張陵彭雾,是天一觀的道長碟刺。 經(jīng)常有香客問我,道長薯酝,這世上最難降的妖魔是什么半沽? 我笑而不...
    開封第一講書人閱讀 56,340評論 1 283
  • 正文 為了忘掉前任,我火速辦了婚禮吴菠,結果婚禮上者填,老公的妹妹穿的比我還像新娘。我一直安慰自己做葵,他們只是感情好占哟,可當我...
    茶點故事閱讀 65,404評論 5 384
  • 文/花漫 我一把揭開白布。 她就那樣靜靜地躺著酿矢,像睡著了一般榨乎。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上瘫筐,一...
    開封第一講書人閱讀 49,749評論 1 289
  • 那天蜜暑,我揣著相機與錄音,去河邊找鬼策肝。 笑死肛捍,一個胖子當著我的面吹牛,可吹牛的內(nèi)容都是我干的之众。 我是一名探鬼主播拙毫,決...
    沈念sama閱讀 38,902評論 3 405
  • 文/蒼蘭香墨 我猛地睜開眼,長吁一口氣:“原來是場噩夢啊……” “哼棺禾!你這毒婦竟也來了恬偷?” 一聲冷哼從身側響起,我...
    開封第一講書人閱讀 37,662評論 0 266
  • 序言:老撾萬榮一對情侶失蹤帘睦,失蹤者是張志新(化名)和其女友劉穎,沒想到半個月后坦康,有當?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體竣付,經(jīng)...
    沈念sama閱讀 44,110評論 1 303
  • 正文 獨居荒郊野嶺守林人離奇死亡,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 36,451評論 2 325
  • 正文 我和宋清朗相戀三年滞欠,在試婚紗的時候發(fā)現(xiàn)自己被綠了古胆。 大學時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點故事閱讀 38,577評論 1 340
  • 序言:一個原本活蹦亂跳的男人離奇死亡,死狀恐怖逸绎,靈堂內(nèi)的尸體忽然破棺而出惹恃,到底是詐尸還是另有隱情,我是刑警寧澤棺牧,帶...
    沈念sama閱讀 34,258評論 4 328
  • 正文 年R本政府宣布巫糙,位于F島的核電站,受9級特大地震影響颊乘,放射性物質(zhì)發(fā)生泄漏参淹。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點故事閱讀 39,848評論 3 312
  • 文/蒙蒙 一乏悄、第九天 我趴在偏房一處隱蔽的房頂上張望浙值。 院中可真熱鬧,春花似錦檩小、人聲如沸开呐。這莊子的主人今日做“春日...
    開封第一講書人閱讀 30,726評論 0 21
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽筐付。三九已至,卻和暖如春颓哮,著一層夾襖步出監(jiān)牢的瞬間家妆,已是汗流浹背。 一陣腳步聲響...
    開封第一講書人閱讀 31,952評論 1 264
  • 我被黑心中介騙來泰國打工冕茅, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留伤极,地道東北人。 一個月前我還...
    沈念sama閱讀 46,271評論 2 360
  • 正文 我出身青樓姨伤,卻偏偏與公主長得像哨坪,于是被迫代替她去往敵國和親。 傳聞我的和親對象是個殘疾皇子乍楚,可洞房花燭夜當晚...
    茶點故事閱讀 43,452評論 2 348

推薦閱讀更多精彩內(nèi)容