445. 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 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.

Follow up: What if you cannot modify the input lists? In other words, reversing the lists is not allowed.

Example:

Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)Output: 7 -> 8 -> 0 -> 7

思路： 把数组的存储换成栈的存储，刚好符合从最后一位开始加的情况。

/** * 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 s1 = new Stack(); Stack s2 = new Stack(); while(l1 != null) { s1.push(l1.val); l1 = l1.next; }; while(l2 != null) { s2.push(l2.val); l2 = l2.next; } 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; ListNode head = new ListNode(sum / 10); head.next = list; list = head; sum /= 10; } return list.val == 0 ? list.next : list; }}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。