Leetcode 2. Add Two Numbers
Very High Frequency
Clarification
Okay, so first I’ll restate the problem. We are given two non-empty linked lists, l1 and l2. Each linked list represents a non-negative integer, but the digits are stored in reverse order.
Example.
Are all node values from 0 to 9?
How long are those lists? Can the two lists have different lengths?
Will there be a leading zero for those two numbers?
Brute-force Approach
A brute force approach could be to convert each linked list into an integer, add them, and then convert the sum back into a linked list. The time complexity should be technically O(n) where n is the length of the longer list. However, we have to do three loops on those three numbers. And the space complexity would be O(n) because we have to create new nodes.
Optimized Approach
The direction of optimization is quite straightforward: how can we reduce the loop and avoid node creation. I believe we can use two pointers approach here.
So what I'll do is to first create a dummy node to make true every node including the head node of those two list has a parent node. Then I need three integer variables to store the digits of l1 and l2 plus the possible carry from the addition. Next I'll start to loop those two lists together. I'll calculate the sum to find the result digit and update the carry. If one list has reached its end, we can consider the digit is 0. Then I'll update the result list in place by finding the next node and updating its value with the new digit. If one list has reached its end, I'll use the node in the other list. If both doesn't reach the end, I'll pick a node from either list. Finally, after the loop, if there is a carry left, we need to create a new node with digit 1.
The time complexity is still O(n) but we only use one loop so in reality it should be faster. The space is O(1) because we don't create new nodes.
Code
/**
* 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) {
ListNode dummy = new ListNode();
ListNode curr = dummy;
int num1 = 0, num2 = 0, carry = 0;
while (l1 != null || l2 != null) {
num1 = l1 == null ? 0 : l1.val;
num2 = l2 == null ? 0 : l2.val;
int sum = num1 + num2 + carry;
if (sum > 9) {
sum %= 10;
carry = 1;
}
else {
carry = 0;
}
ListNode next = l1 == null ? l2 : l1;
next.val = sum;
curr.next = next;
curr = curr.next;
if (l1 != null) l1 = l1.next;
if (l2 != null) l2 = l2.next;
}
if (carry == 1)
curr.next = new ListNode(carry);
return dummy.next;
}
}