Two Sum: Input array is sorted
Two Sum: Input array is sorted
Similar to Question [1. Two Sum], except that the input array is already sorted in ascending order.
You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
Example 1
Input: l1 = [2,4,3], l2 = [5,6,4] Output: [7,0,8] Explanation: 342 + 465 = 807.
Example 2
Input: l1 = [0], l2 = [0] Output: [0]
Example 3
Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9] Output: [8,9,9,9,0,0,0,1]
Of course we could still apply the [Hash table] approach, but it costs us O(n) extra space, plus it does not make use of the fact that the input is already sorted.
O(n log n) runtime, O(1) space – Binary search:
For each element x, we could look up if target – x exists in O(log n) time by applying binary search over the sorted array. Total runtime complexity is O(n log n).
Solution in Java
public class Solution {
// example in leetcode book
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode dummyHead = new ListNode(0);
ListNode p = l1, q= l2, curr = dummyHead;
int carry = 0;
while (p != null || q!= null) {
int x = (p != null) ? p.val : 0;
int y = (q != null) ? q.val : 0;
int digit = carry + x + y;
carry = digit / 10;
curr.next = new ListNode(digit % 10);
curr = curr.next;
if (p != null) p = p.next;
if (q != null) q = q.next;
}
if (carry > 0) {
curr.next = new ListNode(carry);
}
return dummyHead.next;
}
}
Solution in Python
class ListNode(object): def __init__(self, x): self.val = x self.next = None
class Solution(object): def addTwoNumbers(self, l1, l2): carry = 0 # dummy head head = curr = ListNode(0) while l1 or l2: val = carry if l1: val += l1.val l1 = l1.next if l2: val += l2.val l2 = l2.next curr.next = ListNode(val % 10) curr = curr.next carry = int(val / 10) if carry > 0: curr.next = ListNode(carry) return head.next