LeetCode 445. Add Two Numbers II (两数相加 II)

左手的ㄟ右手 2023-08-17 16:45 115阅读 0赞

题目标签：Linked List

题目给了我们两个 数字的linked list，让我们把它们相加，返回一个新的linked list。

因为题目要求不能 reverse，可以把 两个list 的数字都 存入 两个stack。利用了stack的特性，就可以从后面把数字相加，具体看code。

Java Solution:

Runtime:  6 ms, faster than 51.06%

Memory Usage: 45.4 MB, less than 64.71%

完成日期：07/08/2019

关键点：stack

/**
     * 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) {
            
            Stack<Integer> s1 = new Stack<Integer>();
            Stack<Integer> s2 = new Stack<Integer>();
            
            // store two numbers into stacks
            while(l1 != null) {
                s1.push(l1.val);
                l1 = l1.next;
            }
            
            while(l2 != null) {
                s2.push(l2.val);
                l2 = l2.next;
            }
            
            // adding two numbers from stacks
            int sum = 0;
            ListNode list = new ListNode(0);
            
            while(!s1.empty() || !s2.empty()) {
                if(!s1.empty())
                    sum += s1.pop();
                if(!s2.empty())
                    sum += s2.pop();
                
                list.val = sum % 10; // get the value
                ListNode head = new ListNode(sum / 10); // get the carry
                head.next = list;
                list = head;
                
                sum /= 10;
            }
            
            
            // need to check if the head is 0 or not
            return list.val == 0 ? list.next : list;
        }
    }

参考资料：LeetCode Discuss[  
][Link 1]

LeetCode 题目列表 - [LeetCode Questions List][]

题目来源：https://leetcode.com/

转载于:https://www.cnblogs.com/jimmycheng/p/11489371.html

[Link 1]: https://leetcode.com/problems/daily-temperatures/discuss/?currentPage=1&orderBy=recent_activity&query=
[LeetCode Questions List]: http://www.cnblogs.com/jimmycheng/p/7119334.html