[刷题防痴呆] 0445 - 两数相加 II (Add Two

题目地址

https://leetcode.com/problems/add-two-numbers-ii/

题目描述

445. Add Two Numbers II


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]

思路

• 这题与I的区别是, 链表是倒序.
• 两种做法, 第一种, 翻转l1和l2, 相加后再次翻转.
• 第二种, 使用栈.

关键点

• 注意, 翻转会破坏链表结构.

代码

• 语言支持：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) {
        if (l1 == null && l2 == null) {
            return null;
        }
        ListNode m = reverse(l1);
        ListNode n = reverse(l2);

        ListNode ans = addTwo(m, n);
        ListNode reverseAns = reverse(ans);

        return reverseAns;
    }

    private ListNode reverse(ListNode node) {
        ListNode prev = null;
        ListNode cur = node;

        while (cur != null) {
            ListNode next = cur.next;
            cur.next = prev;

            prev = cur;
            cur = next;
        }

        return prev;
    }

    private ListNode addTwo(ListNode l1, ListNode l2) {
        if (l1 == null || l2 == null) {
            return null;
        }
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        int carry = 0;
        
        while (l1 != null && l2 != null) {
            int sum = l1.val + l2.val + carry;
            cur.next = new ListNode(sum % 10);
            carry = sum / 10;
            cur = cur.next;
            l1 = l1.next;
            l2 = l2.next;
        }
        
        while (l1 != null) {
            int sum = l1.val + carry;
            cur.next = new ListNode(sum % 10);
            carry = sum / 10;
            cur = cur.next;
            l1 = l1.next;
        }
        
        while (l2 != null) {
            int sum = l2.val + carry;
            cur.next = new ListNode(sum % 10);
            carry = sum / 10;
            cur = cur.next;
            l2 = l2.next;
        }
        
        if (carry != 0) {
            cur.next = new ListNode(carry);
        }
        
        return dummy.next;
    }    
}

// 使用栈
/**
 * 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) {
        if (l1 == null && l2 == null) {
            return null;
        }
        Deque<Integer> stack1 = new ArrayDeque<>();
        Deque<Integer> stack2 = new ArrayDeque<>();

        while (l1 != null) {
            stack1.push(l1.val);
            l1 = l1.next;
        }

        while (l2 != null) {
            stack2.push(l2.val);
            l2 = l2.next;
        }

        ListNode ans = null;
        int carry = 0;
        while (!stack1.isEmpty() && !stack2.isEmpty()) {
            int num1 = stack1.pop();
            int num2 = stack2.pop();
            int sum = num1 + num2 + carry;
            ListNode node = new ListNode(sum % 10);
            carry = sum / 10;
            node.next = ans;
            ans = node;
        }

        while (!stack1.isEmpty()) {
            int num1 = stack1.pop();
            int sum = num1 + carry;
            ListNode node = new ListNode(sum % 10);
            carry = sum / 10;
            node.next = ans;
            ans = node;          
        }

        while (!stack2.isEmpty()) {
            int num2 = stack2.pop();
            int sum = num2 + carry;
            ListNode node = new ListNode(sum % 10);
            carry = sum / 10;
            node.next = ans;
            ans = node;          
        }      

        if (carry != 0) {
            ListNode node = new ListNode(carry);
            node.next = ans;
            ans = node;     
        }  

        return ans;
    }
}