Add Two Numbers II
给两个链表, 代表数字, 求想加后的链表, 这个题主要是不能翻转链表想加, 那么只能用stack.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 |
/** * 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) { Stack<Integer> st1 = new Stack<>(); Stack<Integer> st2 = new Stack<>(); ListNode p = l1; while(p != null) { st1.push(p.val); p = p.next; } p = l2; while(p != null) { st2.push(p.val); p = p.next; } int carry = 0; ListNode dummy = new ListNode(0); ListNode res = dummy; while(!st1.isEmpty() && !st2.isEmpty()) { int sum = st1.pop() + st2.pop() + carry; carry = sum / 10; dummy.next = new ListNode(sum % 10); dummy = dummy.next; } while(!st1.isEmpty()) { int sum = st1.pop() + carry; carry = sum / 10; dummy.next = new ListNode(sum % 10); dummy = dummy.next; } while(!st2.isEmpty()) { int sum = st2.pop() + carry; carry = sum / 10; dummy.next = new ListNode(sum % 10); dummy = dummy.next; } if(carry != 0) { dummy.next = new ListNode(carry); dummy = dummy.next; } Stack<Integer> resStack = new Stack<>(); res = res.next; while(res != null) { resStack.push(res.val); res = res.next; } ListNode dummyRes = new ListNode(0); ListNode head = dummyRes; while(!resStack.isEmpty()) { dummyRes.next = new ListNode(resStack.pop()); dummyRes = dummyRes.next; } return head.next; } } |