CareerCup

hey, we can form complete decimal number by traversing from head to last node and then taking difference between the two and again breaking them in single digits & storing them in third linked list.....

Use stack

doesn't stack means we are reversing?

I also thought of using stack. But since the question says - "very large" linked list, I don't think using stack will impress the interviewer. We will be duplicating the memory requirement if we use the stack. I hope there is a better alternative to that approach.

ideone[dot]com/Nq3hI

O(n) time and space. I did not choose to use recursion because the question says "very long lists" - which would mean too much of space and func call overhead.

fixed an edge case - ideone[dot]com/MqMZS

ideone[dot]com/btUC3

i am new to this forum so please give feedback on the above code

check this out. I used doubly linked list to collect the result. ideone[dot]com/aYEzA

if allowed to change link list B then

add zeroes at the start of B till both link list length is equal
then start subtracting from head till end.

at any point if A.data>=B.data then the resultant link list will have a node of value
A.data-Ba.data
else if B.data is greater, resultant will have a node of value 10+A.data-B.data. and the value of previous node in the resultant link list will be decremented by 1. ( will need to maintain a previous pointer)

after traversing the whole link list, resultant link list will have the answer.

restore link list B

since we are subtracting only 1 number from A , the borrow required will not propoagate more than 1 digit to right. hence we can subtract from head as well.

eg
A 5 4 2 0 0 9 0 0
B 1 9 9

pad zeroes to B

A 5 4 2 0 0 9 0 0
B 0 0 0 0 0 1 9 9
C is resultant link list

start from head
5>0 C 5
4>0 C 5 4
2>0 C 5 4 2
0>=0 C 5 4 2 0
0>=0 C 5 4 2 0 0
9>1 C 5 4 2 0 0 8
0<9 hence v=next value will be 10 + 0 -9 =1 and prev node is decremented. hence 8 becomes 7 C is 5 4 2 0 0 7 1
0<9 similar to above value is 10 +0 -9 =1 and previous 1 becomes 0

C is 5 4 2 0 0 7 0 1

this is assuming A>B if not which we can come to know while examining the head values
call same function with the lists swapped and will need to append - sign at head.

Why cannt we convert it in to decimal subtract it and then convert back to linked list

converting will take only o(n) and the subtracting o(1) and again converting o(n).

Since, the linked lists can be very large, we obviously cannot convert them into a number and subtract using a unary minus. So the trick to solve this question is to traverse the list and subtract the value of list1 with the value of list2 and also subtract the borrow. If the result is negative, add 10 to the final result.

;lk;lk

let we are subtracting (A - B) List. So We can create an array having entries of index where numbers in List A is greater then List B. And we can subtract numbers acording to that array entries. This will take total of O(n)Time and O(n) Space.

let we are subtracting (A - B) List. So We can create an array having entries of index where numbers in List A is greater then List B. And we can subtract numbers acording to that array entries. This will take total of O(n)Time and O(n) Space.

I was thinking something along the lines of.

Start identifying the both ll's length at the same time.
If you see one of them ending
stop
////now you know the length of the smaller one. Let = X
Now identify the X digits from the end for the bigger ll. (Using one pointer and another pointer legging behind by X traversing once. It's O(n))
Do math.

From what I see here complexity is minimized, actually its O(n) and no extra space.

I was thinking something along the lines of.

Start identifying the both ll's length at the same time.
If you see one of them ending
stop
////now you know the length of the smaller one. Let = X
Now identify the X digits from the end for the bigger ll. (Using one pointer and another pointer legging behind by X traversing once. It's O(n))
Do math.

From what I see here complexity is minimized, actually its O(n) and no extra space.

//find the length of both list l1, l2 
//append l1-l2 nodes in the second list  in front
fun(list a, list b){
	if(a==null)
		return 0;
	int borrow=fun(a.next,b.next,c)
	Node newNode=new Node();
	if(a.data>b.data){
		newNode.data=a.data-b.data-borrow;
		newNode.next=c;//front insertion
		c=newNode;
		return 0;
	}
	else if(a.data==b.data){
		if(borrow==0){
			newNode.data=0;
			newNode.next=c;
		    c=newNode;
			return 0;
		}
		else{
			newNode.data=9;
			newNode.next=c;
		    c=newNode;
			return 1;
		}
		else{
			newNode.data=a.data+10-b.data-borrow
			newNode.next=c;
		    c=newNode;
			return 1;
		}
	}

}