Add Two Numbers || LeetCode-2

Problem link： https://leetcode.com/problems/3sum-closest/#/description

You are given two non-empty linked lists representing two non-negative integers. 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.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)

Output: 7 -> 0 -> 8

<问题描述>

给定两个非负整形的非空链表，整数的每一位以相反的顺序存储在链表中

你可以假定两个整数都没有前导的零

给出的addTwoNumbers函数应该以链表形式返回两个整数的和

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)

输出：7 -> 0 -> 8

Approach #Solution

Analysis

本题思路很简单，按照加法原理从末尾到首位，每一位对齐相加即可。关键在于如何处理不同长度的数字，以及进位和最高位的判断。若有一个为null时，返回不为null的那个ListNode和进位相加的值；若都不为null时，返回两个ListNode和进位相加的值。

Code

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        if (l1 == null && l2 == null) {
            return null;
        }
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }

        // resultList, resultNode, resultNext必须初始化，否则编译不通过
        ListNode resultList = null; // 返回链表
        ListNode resultNode = null; // 头节点
        ListNode resultNext = null; // 每次新插入的节点
        int carry = 0; // 进位

        while(l1 != null && l2 != null) {
            resultNext = new ListNode(l1.val + l2.val + carry);
            carry = resultNext.val / 10; // 计算进位
            resultNext.val = resultNext.val % 10; // 计算该位的数值

            if (resultList == null) { // 头节点为空，即插入的节点为返回链表的第一个节点时
                resultNode = resultNext;
                resultList = resultNext;
            } else { // 头节点不为空
                resultNode.next = resultNext;
                resultNode = resultNext;
            }
            l1 = l1.next;
            l2 = l2.next;
        }

        while (l1 != null) { // 链表l1比链表l2长，处理链表l1的高位
            resultNext = new ListNode(l1.val + carry);
            carry = resultNext.val / 10;
            resultNext.val = resultNext.val % 10;
            resultNode.next = resultNext;
            resultNode = resultNext;
            l1 = l1.next;
        }

        while (l2 != null) { // 链表l2比链表l1长，处理链表l2的高位
            resultNext = new ListNode(l2.val + carry);
            carry = resultNext.val / 10;
            resultNext.val = resultNext.val % 10;
            resultNode.next = resultNext;
            resultNode = resultNext;
            l2 = l2.next;
        }

        if (carry > 0) { // 最高位产生进位，需要新建节点进行存储
            resultNext = new ListNode(carry);
            resultNode.next = resultNext;
        }

        return resultList;
    }

    // 递归写法 参考：https://segmentfault.com/a/1190000002986101
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        return addList(l1, l2, 0);
    }

    public ListNode addList(ListNode l1, ListNode l2, int carry){
        if(l1 == null && l2 == null){
            return carry == 0? null : new ListNode(carry);
        }

        if(l1 == null && l2 != null){
            l1 = new ListNode(0);
        }
        
        if(l2 == null && l1 != null){
            l2 = new ListNode(0);
        }
        
        int sum = l1.val + l2.val + carry;
        ListNode curr = new ListNode(sum % 10);
        curr.next = addList(l1.next, l2.next, sum / 10);
        return curr;
    }
}

Complexity

时间复杂度：O(n)

时间复杂度：O(n)