akumarb2010
BAN USER- 0of 0 votes
Answerssum the linked lists
- akumarb2010 in India
1->2->3
4->5
result is 1->6->8| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer - 0of 0 votes
AnswersGiven: Suppose balanced binary tree(T) is given.
- akumarb2010 in United States for Elastic Mapreduce
Def'n: sum of the tree is defined as sum of the values of all it's nodes.
Question: Write a method which returns sub-tree whose sum is maximum.| Report Duplicate | Flag | PURGE
Amazon SunGard Software Engineer / Developer Algorithm
Yes, you are correct.
Below one will work, but I need to refactor
public static ListNode reverse(ListNode head) {
ListNode previous = null;
ListNode current = head;
ListNode forward;
while (current != null) {
forward = current.next;
current.next = previous;
previous = current;
current = forward;
}
return previous;
}
public static ListNode sumOfTheLists(ListNode head1, ListNode head2)
{
if(head1 == null && head2 == null)
{
return null;
}
if(head1 == null && head2 != null)
{
return head2;
}
if(head1 != null && head2 == null)
{
return head1;
}
LinkedList result = new LinkedList();
ListNode rhead1 = reverse(head1);
ListNode rhead2 = reverse(head2);
int temp = 0;
while(rhead1 != null || rhead2 != null)
{
if(rhead1 != null && rhead2 != null)
{
temp += (Integer)rhead1.element+(Integer)rhead2.element;
if(temp%10 != 0 || temp == 10 )
{
result.insertLast(temp%10);
temp = temp/10;
}
else
{
result.insertLast(temp);
temp = 0;
}
rhead1 = rhead1.next;
rhead2 = rhead2.next;
}
else
{
if(rhead1 != null)
{
temp += (Integer)rhead1.element;
if(temp%10 != 0 || temp == 10 )
{
result.insertLast(temp%10);
temp = temp/10;
}
else
{
result.insertLast(temp);
temp = 0;
}
rhead1 = rhead1.next;
}
if(rhead2 != null)
{
temp += (Integer)rhead2.element;
if(temp%10 != 0 || temp == 10 )
{
result.insertLast(temp%10);
temp = temp/10;
}
else
{
result.insertLast(temp);
temp = 0;
}
rhead1 = rhead2.next;
}
}
}
return reverse(result.head);
}
It will work. Following is out put
List1: 1 9 5
List2: 1 5
Result sum list: 1 10 10
It will work for it.
List1: 1 9 5
List2: 1 5
Result sum list: 1 10 10
Is there any other Optimal solution?
Time complexity O(max(m,n)). Space Complexity: No extra space.
public static LinkedList sumOfTwoLists(LinkedList list1, LinkedList list2)
{
if(list1 == null)
{
return list2;
}
if(list2 == null)
{
return list1;
}
LinkedList result = null;
int diffSize = list2.listSize();
if(diffSize < list1.listSize())
{
diffSize = list1.listSize() - diffSize;
ListNode temp1 = list1.head;
result = new LinkedList(temp1.element);
while(temp1.next != null && --diffSize > 0)
{
result.insertLast(temp1.next.element);
temp1 = temp1.next;
}
ListNode temp2 = list2.head;
while(temp1.next != null && temp2 != null )
{
result.insertLast((Integer)temp1.next.element+(Integer)temp2.element);
temp1 = temp1.next;
temp2 = temp2.next;
}
}
else if(diffSize > list1.listSize())
{
diffSize = diffSize - list1.listSize();
ListNode temp1 = list2.head;
result = new LinkedList(temp1.element);
while(temp1.next != null && --diffSize > 0)
{
result.insertLast(temp1.next.element);
}
ListNode temp2 = list1.head;
while(temp1.next != null && temp2 != null )
{
result.insertLast((Integer)temp1.next.element+(Integer)temp2.element);
temp1 = temp1.next;
temp2 = temp2.next;
}
}
else {
ListNode temp1 = list2.head;
ListNode temp2 = list1.head;
result = new LinkedList(new Integer((Integer)temp1.element+(Integer)temp2.element));
while(temp1.next != null && temp2.next != null )
{
result.insertLast((Integer)temp1.next.element+(Integer)temp2.next.element);
temp1 = temp1.next;
temp2 = temp2.next;
}
}
return result;
}
public int listSize() {
int size = 0;
ListNode temp = this.head;
while (temp != null) {
size++;
temp = temp.next;
}
return size;
}
This is working in all cases:
- akumarb2010 December 28, 2011