445. Add Two Numbers II

难度: Medium

题目描述

You are given two non-empty linked lists representing two non-negative integers. The most significant digit comes first and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.

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

 

Example 1:

Input: l1 = [7,2,4,3], l2 = [5,6,4]
Output: [7,8,0,7]

Example 2:

Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [8,0,7]

Example 3:

Input: l1 = [0], l2 = [0]
Output: [0]

 

Constraints:

• The number of nodes in each linked list is in the range [1, 100].
• 0 <= Node.val <= 9
• It is guaranteed that the list represents a number that does not have leading zeros.

 

Follow up: Could you solve it without reversing the input lists?

解题思路

代码实现

解决方案

java

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

        LinkedList<Integer> first = new LinkedList<>();
        LinkedList<Integer> second = new LinkedList<>();
        LinkedList<Integer> res = new LinkedList<>();
        ListNode p1 = l1;
        ListNode p2 = l2;
        while (p1 != null) {
            first.push(p1.val);
            p1 = p1.next;
        }
        while (p2 != null) {
            second.push(p2.val);
            p2 = p2.next;
        }
        int carry = 0;
        while (!first.isEmpty() || !second.isEmpty()) {
            int f = 0;
            if (!first.isEmpty()) {
                f = first.pop();
            }
            int s = 0;
            if (!second.isEmpty()) {
                s = second.pop();
            }
            
            res.push((carry + f + s) % 10);
            carry = (carry + f + s) / 10;

        }
        if(carry!=0){
            res.push(carry);
        }
        ListNode root = new ListNode();
         ListNode head = root;
        while(!res.isEmpty()){
            int e = res.pop();
            ListNode temp = new ListNode(e);
            root.next = temp;
            root = temp;
        }
        return head.next;

    }
}