Added solution for adding number II

anxious-coder-lhs · anxious-coder-lhs · commit b3c41cb4fdc9 · 2020-11-06T16:01:57.000+05:30
diff --git a/README.md b/README.md
@@ -62,6 +62,7 @@ Happy to accept any contributions to this in any langugage.
 3. [Leet Code 297 - Serialize Deserialize Binary Tree](https://leetcode.com/problems/serialize-and-deserialize-binary-tree/) | [Solution](./level_hard/SerializeDeserializeBinaryTree.ts)
 4. [Leet Code 428 - Serialize Deserialize N-Ary Tree](https://leetcode.com/problems/serialize-and-deserialize-n-ary-tree/) | [Solution](./level_hard/SerializeDeserializeNAryTree.ts)
 5. [Leet Code 25 - Reverse Linked List k Nodes at a time](https://leetcode.com/problems/reverse-nodes-in-k-group/) | [Solution](./level_hard/LeetCode%2025_Reverse%20Linked%20List%20K%20Nodes.ts)
+6. [Leet Code 445 - Add Numbers II](https://leetcode.com/problems/add-two-numbers-ii/) | [Solution 1](./level_medium/LeetCode%20445_Add%202%20Numbers_1.ts) | [Solution 2](./level_medium/LeetCode%20445_Add%202%20Numbers_2.ts)
 
 ## Sorting
 1. Bubble Sort | [Solution](./sorting/Sort_Bubble.js)
diff --git a/level_medium/LeetCode 445_Add 2 Numbers_1.ts b/level_medium/LeetCode 445_Add 2 Numbers_1.ts
@@ -0,0 +1,54 @@
+/**
+ * Definition for singly-linked list.
+ * class ListNode {
+ *     val: number
+ *     next: ListNode | null
+ *     constructor(val?: number, next?: ListNode | null) {
+ *         this.val = (val===undefined ? 0 : val)
+ *         this.next = (next===undefined ? null : next)
+ *     }
+ * }
+ */
+/**
+ * Leet Code 445.
+ * Solution uses O(n) space for each linked list to store the reverse items into a stack, so that the least
+ * significant digit can be read first and so on. Alternatively, you can create another linked list in reverse
+ * order to reverse it in place.
+ * 
+ * Time: O(n) for navigation (n max of all items in the linked lists)
+ * Space: O(n) for storing all items in reverse apart from the final numbers.
+ * 
+ * @param l1 
+ * @param l2 
+ */
+function addTwoNumbers(l1: ListNode | null, l2: ListNode | null): ListNode | null {
+    const l1Stack: number[] = createStack(l1);
+    const l2Stack: number[] = createStack(l2);
+    const result: number[] = [];
+    let carry = 0;
+    while(l1Stack.length > 0 || l2Stack.length > 0) {
+        const sum = (l1Stack.pop() || 0) + (l2Stack.pop() || 0) + carry;
+        carry = Math.floor(sum / 10);
+        result.push(sum % 10);
+    }
+    
+    if (carry > 0) result.push(carry);
+    return stackToList(result);
+};
+
+function stackToList(result: number[]) {
+    const head: ListNode = new ListNode(result.pop(), null);
+    let curr = head;
+    while(result.length > 0) {
+        const item = result.pop();
+        curr.next = new ListNode(item, null);
+        curr = curr.next;
+    }
+    return head;
+}
+
+function createStack(l1: ListNode | null, stack: number[] = []): number[] {
+    if (l1 === null) return stack
+    stack.push(l1.val)
+    return createStack(l1.next, stack)
+}
diff --git a/level_medium/LeetCode 445_Add 2 Numbers_2.ts b/level_medium/LeetCode 445_Add 2 Numbers_2.ts
@@ -0,0 +1,107 @@
+/**
+ * Definition for singly-linked list.
+ * class ListNode {
+ *     val: number
+ *     next: ListNode | null
+ *     constructor(val?: number, next?: ListNode | null) {
+ *         this.val = (val===undefined ? 0 : val)
+ *         this.next = (next===undefined ? null : next)
+ *     }
+ * }
+ */
+
+ /**
+  * Leet Code 445.
+  * 
+  * Solution uses an O(1) space aimed to reduce the required space for reversal or virtual reversal. It rather uses
+  * the length of the linked list to identify when a padding can be used and when can it be skipped. This step is done
+  * without the help of additional carry, since carry needs to be added in the reverse order.
+  * 
+  * To adjust the carry pointer, we need to reverse the list, adjust the carry and reverse again.
+  * 
+  * O(n) time for run-time, O(1) for space.
+  * 
+  * @param l1 
+  * @param l2 
+  */
+function addTwoNumbers(l1: ListNode | null, l2: ListNode | null): ListNode | null {
+    
+    // Finding the length of each linked list.
+    let l1Length = length(l1);
+    let l2Length = length(l2);
+    
+    let resultCurr: ListNode | null = new ListNode(0, null), resultHead = resultCurr, lastCurr: ListNode | null = resultCurr;
+    
+    // Adding items with prefixes attached, not using the carry.
+    while(l1Length >= 0 && l2Length >= 0 && l1 !== null && l2 !== null) {
+        if (l1Length > l2Length) {
+            // L1 has more items than l2, lets pull from l1 and add 0 for l2.
+            resultCurr.val = l1.val;
+            l1 = l1.next;
+            resultCurr.next = new ListNode(0, null)    
+            l1Length--;
+        } else if (l1Length < l2Length) {
+            // L2 has more items than l1, lets pull from l2 and add 0 for l1.
+            resultCurr.val = l2.val;
+            l2 = l2.next;
+            resultCurr.next = new ListNode(0, null)
+            l2Length--
+        } else {
+            // Both have equal items, lets add.
+            resultCurr.val = l2.val + l1.val;
+            l2 = l2.next; l1 = l1.next;
+            resultCurr.next = new ListNode(0, null)
+            l2Length--; l1Length--;
+        }
+
+        lastCurr = resultCurr;
+        resultCurr = resultCurr.next;
+    }
+    lastCurr.next = null;
+    
+    let newHead = reverseLinkedList(resultHead);
+    
+    // Adjust the carry now.
+    adjustCarry(newHead)
+    
+    // Reverse the list and return.
+    newHead = reverseLinkedList(newHead);
+    
+    return newHead;
+};
+
+function adjustCarry(list: ListNode | null) {
+    let curr = list, last = null, carry = 0;
+    while(curr !== null) {
+        const val = curr.val + carry;
+        curr.val = val % 10;
+        carry = Math.floor(val / 10)
+        last = curr;
+        curr = curr.next;
+    }
+    
+    // Add the pending carry to a new node.
+    if (carry > 0 && last !== null) {
+        last.next = new ListNode(carry, null);
+    }
+}
+
+function length(l1: ListNode | null) {
+    let length = 0, curr = l1;
+    while(curr !== null) {
+        length++
+        curr = curr.next;
+    }
+    return length;
+}
+
+function reverseLinkedList(l1: ListNode | null) {
+    let curr = l1, last: ListNode | null = null;
+    while(curr !== null) {
+        const next = curr.next;
+        curr.next = last;
+        last = curr;
+        curr = next;
+    }
+    return last;
+}
