索引

1. 思路1：基本加法规则
2. 思路2：移花接木法。。。

// Runtime: 116 ms

var addTwoNumbers = function(l1, l2) {

    let dummy = { next: null }, // 结果链表的head指针

        tail = dummy, // tail总是指向dummy的末尾元素,以便在链表尾插入新元素

        flag = false, // flag标示是否需要进位

        sum;

    let init = () => { // 初始化,因为保证非空,所以首位总是存在的(可能为0)

        sum = l1.val + l2.val;

        tail.next = new ListNode(sum % 10);

        // 为下一位的计算做准备

        flag = sum >= 10;

        l1 = l1.next;

        l2 = l2.next;

        // 保持tail性质不变

        tail = tail.next;

    };

    let work = () => {

        let v1, v2;

        while (l1 || l2 || flag) {

            // 统一化处理,不用判断谁空谁不空

            v1 = l1 ? l1.val : 0;

            v2 = l2 ? l2.val : 0;

            sum = v1 + v2 + (flag ? 1 : 0);

            tail.next = new ListNode(sum % 10);

            // 为下一位的计算做准备

            flag = sum >= 10;

            l1 = l1 ? l1.next : null;

            l2 = l2 ? l2.next : null;

            // 保持tail性质不变

            tail = tail.next;

        }

    };

    init();

    work();

    return dummy.next;

};

/**

 * Definition for singly-linked list.

 * struct ListNode {

 *     int val;

 *     struct ListNode *next;

 * };

 */

struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {

    struct ListNode *l3 = malloc(sizeof(struct ListNode));

    struct ListNode *tail = l3; 

    int sum = l1->val + l2->val;

    tail->val = sum % ;

    int flag = sum >= ;

    l1 = l1->next;

    l2 = l2->next;

    int v1, v2;

    while (l1 || l2 || flag) {

        v1 = l1 ? l1->val : ;

        v2 = l2 ? l2->val : ;

        sum = v1 + v2 + (flag ?  : );

        tail->next = malloc(sizeof(struct ListNode));

        tail = tail->next;

        tail->val = sum % ;

        flag = sum >= ;

        l1 = l1 ? l1->next : NULL;

        l2 = l2 ? l2->next : NULL;

    }

    tail->next = NULL; // 这句话是必要的！否则提交后会有运行时错误。

    return l3;

}

C语言版本

/**

 * Definition for singly-linked list.

 * public class ListNode {

 *     int val;

 *     ListNode next;

 *     ListNode(int x) { val = x; }

 * }

 */

class Solution {

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {

        ListNode ans = new ListNode(0), tail = ans;

        boolean flag = false; // 当前位是否需要进位

        // 保持一个循环不变式：

        // ans的前面n位为l1与l2前n位相加的正确结果

        // l1与l2要么为空要么指向当前/即将计算位

        // 初始化

        int sum = l1.val + l2.val + (flag ? 1 : 0);

        tail.val = sum % 10;

        flag = sum >= 10;

        l1 = l1.next;

        l2 = l2.next;

        // 保持

        int v1, v2; // l1.val与l2.val不能再直接用，可能为空

        while (flag || l1 != null || l2 != null) {

            if (l1 == null) {

                v1 = 0;

            } else {

                v1 = l1.val;

                l1 = l1.next;

            }

            if (l2 == null) {

                v2 = 0;

            } else {

                v2 = l2.val;

                l2 = l2.next;

            }

            sum = v1 + v2 + (flag ? 1 : 0);

            tail.next = new ListNode(sum % 10);

            flag = sum >= 10;

            tail = tail.next;

        }

        // 终止

        return ans;

    }

}

Java版本

// 不创建新链表,直接把结果存到l1上,并对多出来的部分做"嫁接"处理

// Runtime: 112 ms, faster than 99.52% of JavaScript online submissions for Add Two Numbers.

var addTwoNumbers2 = function(l1, l2) {

    let dummy = { next: l1 }, // 结果链表的head指针

        tail = dummy, // tail总是指向l1的前继元素(也就是dummy的尾元素)，以便在链尾插入链表/新元素

        flag = false, // flag标示下一位的计算是否需要进位

        sum;

    let init = () => { // 初始化,因为保证非空,所以首位总是存在的

        sum = l1.val + l2.val;

        l1.val = sum % 10;

        // 为下一位的计算做准备

        flag = sum >= 10;

        l1 = l1.next;

        l2 = l2.next;

        // 保持tail性质不变

        tail = tail.next;

    };

    let status1 = () => { // 处理等长的那部分

        while (l1 && l2) {

            sum = l1.val + l2.val + (flag ? 1 : 0);

            l1.val = sum % 10;

            // 为下一位的计算做准备

            flag = sum >= 10;

            l1 = l1.next;

            l2 = l2.next;

            // 保持tail性质不变

            tail = tail.next;

        }

    };

    let status2 = () => { // 处理多出来的部分

        // 如果l2更长,直接移植到l1

        if (l2) {

            l1 = tail.next = l2;

        }

        // 处理进位

        while (l1 && flag) {

            sum = l1.val + 1;

            l1.val = sum % 10;

            // 为下一位的计算做准备

            flag = sum >= 10;

            l1 = l1.next;

            // 保持tail性质不变

            tail = tail.next;

        }

        if (flag) {

            tail.next = new ListNode(1);

        }

    };

    init();

    status1();

    status2();

    return dummy.next;

};