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
ไปฃ็
Approach #1 Two Stack
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */classSolution {publicListNodeaddTwoNumbers(ListNode l1,ListNode l2) {Stack<Integer> s1 =newStack<Integer>();Stack<Integer> s2 =newStack<Integer>();while (l1 !=null) {s1.push(l1.val); l1 =l1.next; }while (l2 !=null) {s2.push(l2.val); l2 =l2.next; }int sum =0;ListNode head =newListNode(0);while (!s1.empty() ||!s2.empty()) {if (!s1.empty()) sum +=s1.pop();if (!s2.empty()) sum +=s2.pop();head.val= sum %10;ListNode node =newListNode(sum /10);node.next= head; head = node; sum /=10; }returnhead.val==0?head.next: head; }}