一、題目說明

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
查看原題;
查看我的Github項目地址;
題目：給定兩個代表非負數(shù)的鏈表，鏈表中的節(jié)點分別代表個十百等位數(shù)，求這個兩個數(shù)的和，結果也用鏈表表示。

二、解題

2.1 遍歷兩個鏈表

遍歷兩個鏈表，把各個位數(shù)相加，注意進位就可以了。
代碼如下：

public static ListNode addTwoNumbersBySigLoop(ListNode l1, ListNode l2) {
    if (l1 == null) {
        return l2;
    } else if (l2 == null) {
        return l1;
    }
    ListNode list = null;
    ListNode next = null;
    int sum = 0;
    int b = 0;
    while (l1 != null || l2 != null) {
        if (l1 != null) {
            sum = l1.val;
            l1 = l1.next;
        }
        if (l2 != null) {
            sum += l2.val;
            l2 = l2.next;
        }
        sum += b;
        if (sum > 9) {
            sum -= 10;
            b = 1;
        } else {
            b = 0;
        }
        if (list == null) {
            list = new ListNode(sum);
            next = list;
        } else {
            next.next = new ListNode(sum);
            next = next.next;
        }
        sum = 0;
    }
    if (b == 1) {
        next.next = new ListNode(b);
    }
    return list;
}

2.2 遍歷較短的鏈表

另一種方式只遍歷較短的鏈表，剩下的較長鏈表可以直接添加。
代碼如下：

if (l1 == null) {
            return l2;
        } else if (l2 == null) {
            return l1;
        }
        ListNode list = null;
        ListNode next = null;
        ListNode cl1 = l1.next;
        ListNode cl2 = l2.next;
        while (true) {
            if (cl1 == null) {
                cl1 = l1;
                cl2 = l2;
                break;
            } else if (cl2 == null) {
                cl1 = l2;
                cl2 = l1;
                break;
            } else {
                cl1 = cl1.next;
                cl2 = cl2.next;
            }
        }

        int sum = 0;
        int b = 0;
        while (cl1 != null) {
            sum = cl1.val + cl2.val + b;
            cl1 = cl1.next;
            cl2 = cl2.next;

            if (sum > 9) {
                sum -= 10;
                b = 1;
            } else {
                b = 0;
            }

            if (list == null) {
                list = new ListNode(sum);
                next = list;
            } else {
                next.next = new ListNode(sum);
                next = next.next;
            }

            sum = 0;
        }

        next.next = cl2;
        while (b == 1) {
            if (cl2 == null) {
                next.next = new ListNode(b);
                break;
            }
            sum = cl2.val + b;
            if (sum > 9) {
                sum -= 10;
                b = 1;
            } else {
                b = 0;
            }
            cl2.val = sum;
            cl2 = cl2.next;
            next = next.next;
        }
        return list;

三、總結

主要考察對鏈表的操作，對鏈表這種數(shù)據(jù)結構的遍歷、增、刪等操作應該熟練。