Python 3 solution using top down design


#1

def subtract(self, A):
def inverse_half(N,l):
if l<2:
return N
_cur = N.next #2
_prev=N #1
_next=_cur.next #3
while (l-1):
_cur.next=_prev
_prev=_cur
_cur=_next
_next=_next.next
l-=1
N.next=_cur
return _prev
def sub_half(N,lenght):
idx1=N
idx2=N
begining_idx = 1 + lenght//2 if (lenght%2 ==1) else lenght//2
for _ in range(begining_idx):
idx2=idx2.next
for _ in range(lenght//2):
idx1.val = idx2.val - idx1.val
idx1=idx1.next
idx2=idx2.next
return N
lenght=0
p=A
while (p!=None):
lenght+=1
p=p.next
A = inverse_half(A,lenght//2)
A = sub_half(A,lenght)
return inverse_half(A,lenght//2)