445. Add Two Numbers II
by Botao Xiao
445. Add Two Numbers II
Question
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
Solution
- Method 1: Reverse List
```Java
/**
- 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) { // Reverse both list; ListNode pre = null, next = l1.next, cur = l1; while(cur != null){ next = cur.next; cur.next = pre; pre = cur; cur = next; } l1 = pre; pre = null; next = l2.next; cur = l2; while(cur != null){ next = cur.next; cur.next = pre; pre = cur; cur = next; } l2 = pre; ListNode dummy = new ListNode(0); cur = dummy; int carry = 0; while(l1 != null || l2 != null){ int sum = 0; if(l1 != null && l2 != null){ sum = l1.val + l2.val + carry; l1 = l1.next; l2 = l2.next; }else if(l1 != null){ sum = l1.val + carry; l1 = l1.next; }else{ sum = l2.val + carry; l2 = l2.next; } cur.next = new ListNode(sum % 10); carry = sum / 10; cur = cur.next; } if(carry == 1) cur.next = new ListNode(1); pre = null; cur = dummy.next; next = cur.next; while(cur != null){ next = cur.next; cur.next = pre; pre = cur; cur = next; } return pre; } } ```
- Method 2: Stack
```Java
/**
- 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; } ListNode pre = null, cur = null; int carry = 0; while(!s1.isEmpty() || !s2.isEmpty()){ int sum = carry; if(!s1.isEmpty() && !s2.isEmpty()){ sum += s1.pop() + s2.pop(); }else if(!s1.isEmpty()){ sum += s1.pop(); }else sum += s2.pop(); cur = new ListNode(sum % 10); cur.next = pre; pre = cur; carry = sum / 10; } if(carry == 1){ cur = new ListNode(1); cur.next = pre; } return cur; } } ```
- Method 3: Recursion
```Java
/**
- 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) { // Get the size of the two lists. int size1 = getLength(l1), size2 = getLength(l2); ListNode head = new ListNode(1); // Assume current node is 1, we will check is next node is over 10. head.next = size1 > size2 ? createNext(l1, l2, size1 - size2): createNext(l2, l1, size2 - size1); if(head.next.val > 9){ head.next.val %= 10; return head; } return head.next; } private int getLength(ListNode node){ int count = 0; while(node != null){ count++; node = node.next; } return count; } private ListNode createNext(ListNode l1, ListNode l2, int offset){ if(l1 == null) return null; // Create current node. ListNode result = offset == 0 ? new ListNode(l1.val + l2.val): new ListNode(l1.val); // Create next node. ListNode next = offset == 0 ? createNext(l1.next, l2.next, 0): createNext(l1.next, l2, offset - 1); result.next = next; if(next != null && next.val > 9){ next.val %= 10; result.val += 1; } return result; } } ```
Reference
Subscribe via RSS