我是小小強(qiáng)某抓，這是我的第8篇原創(chuàng)文章揖膜，閱讀需要大約10分鐘。

題目

LintCode:鏈表求和

描述

你有兩個(gè)用鏈表代表的整數(shù)姿锭，其中每個(gè)節(jié)點(diǎn)包含一個(gè)數(shù)字塔鳍。數(shù)字存儲(chǔ)按照在原來(lái)整數(shù)中相反的順序，使得第一個(gè)數(shù)字位于鏈表的開(kāi)頭呻此。寫(xiě)出一個(gè)函數(shù)將兩個(gè)整數(shù)相加轮纫，用鏈表形式返回和。

樣例

給出兩個(gè)鏈表 3->1->5->null和5->9->2->null趾诗，返回8->0->8->null

思路

題目中要求從鏈表頭節(jié)點(diǎn)開(kāi)始蜡感，按位相加蹬蚁，同時(shí)進(jìn)位。那就可以構(gòu)造一個(gè)鏈表郑兴，存放相加結(jié)果犀斋，同時(shí)用一個(gè)臨時(shí)變量存放鏈表相加之和，如果大于10情连，則設(shè)置進(jìn)位標(biāo)志叽粹。最后結(jié)束時(shí)判斷進(jìn)位標(biāo)志是否為0，不為0却舀，則需要再進(jìn)位虫几。

實(shí)現(xiàn)

1. java實(shí)現(xiàn)

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;      
 *     }
 * }
 */
public class Solution {
    /**
     * @param l1: the first list
     * @param l2: the second list
     * @return: the sum list of l1 and l2 
     */
    public ListNode addLists(ListNode l1, ListNode l2) {
        // write your code here
        int flag = 0;
        int a = 0;
        ListNode ln = new ListNode(0);
        ListNode tmpln = ln, tmpl1 = l1, tmpl2 = l2, tmp = null;
        if (l1 == null){
            return l2;
        }
        if (l2 == null){
            return l1;
        }
        if (l1 == null && l2 == null) {
            return null;
        }
        while (tmpl1 != null || tmpl2 != null){
            if (tmpl1 != null){
                a += tmpl1.val;
            }
            if (tmpl2 != null){
                a += tmpl2.val;
            }
            if (flag > 0) {
                a += flag;
            }
            if( a>=10 ) {
                flag = 1;
                a -= 10;
            }
            else
                flag = 0;
            tmp = new ListNode(a);
            tmpln.next = tmp;
            tmpln = tmp;
            tmpln.next = null;
            a = 0;
            if (tmpl1 != null)
                tmpl1 = tmpl1.next;
            if (tmpl2 != null)
                tmpl2 = tmpl2.next;
        }
        if (flag > 0){
            tmp = new ListNode(1);
            tmpln.next = tmp;
        }
        return ln.next;
    }
}

2. 結(jié)果分析
   結(jié)果：結(jié)果通過(guò)了LintCode的要求。
   分析：這種實(shí)現(xiàn)比較好理解挽拔，但是實(shí)現(xiàn)起來(lái)卻沒(méi)什么巧妙之處辆脸。

其它優(yōu)化參考

LeetCode discuss

優(yōu)秀代碼

public class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode c1 = l1;
        ListNode c2 = l2;
        ListNode sentinel = new ListNode(0);
        ListNode d = sentinel;
        int sum = 0;
        while (c1 != null || c2 != null) {
            sum /= 10;
            if (c1 != null) {
                sum += c1.val;
                c1 = c1.next;
            }
            if (c2 != null) {
                sum += c2.val;
                c2 = c2.next;
            }
            d.next = new ListNode(sum % 10);
            d = d.next;
        }
        if (sum / 10 == 1)
            d.next = new ListNode(1);
        return sentinel.next;
    }
}