Problem: 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.
Note: The two numbers do not contain any leading zero, except the number 0 itself.
Example:
Input: (1 -> 2 -> 3 -> 4) + (5 -> 6 -> 7) Output: 1 -> 8 -> 0 -> 1
Approach: We can solve it recursively but I am using two stacks here. Approach is straight forward and can be understood by just looking at the implementation.
Implementation in C#:
public ListNode AddTwoNumbers(ListNode l1, ListNode l2)
{
Stack<int> l1Stack = new Stack<int>();
Stack<int> l2Stack = new Stack<int>();
while(l1 != null)
{
l1Stack.Push(l1.val);
l1 = l1.next;
}
while(l2 != null)
{
l2Stack.Push(l2.val);
l2 = l2.next;
}
ListNode head = null;
int carry = 0;
while(l1Stack.Count > 0 && l2Stack.Count > 0)
{
int l1Num = l1Stack.Pop();
int l2Num = l2Stack.Pop();
int result = l1Num + l2Num + carry;
head = new ListNode(result % 10, head);
carry = result / 10;
}
if (l1Stack.Count > 0)
{
AddSingleNumWithCarry(l1Stack, ref head, carry);
}
else if (l2Stack.Count > 0)
{
AddSingleNumWithCarry(l2Stack, ref head, carry);
}
else if (carry > 0)
{
AddSingleNumWithCarry(null, ref head, carry);
}
return head;
}
private void AddSingleNumWithCarry(Stack<int> stack, ref ListNode head, int carry)
{
if (stack != null)
{
while (stack.Count > 0)
{
int result = stack.Pop() + carry;
head = new ListNode(result % 10, head);
carry = result / 10;
}
}
if (carry > 0)
{
head = new ListNode(carry, head);
}
}
Complexity: O(n)
No comments:
Post a Comment