from random import randrange

class Noeud(object):

def __init__(self, valeur, suivant=None):

self.val = valeur

self.suiv = suivant

# self.listUpdate()

def __repr__(self):

res = str(self.val) + " "

if (self.suiv != None):

res += str(self.suiv)

return res

def __lt__(self, autre):

return self.val < autre.val

"""

def __add__(self, a):

return repr(self) + repr(a)

def listUpdate(self):

if self.suiv == None:

self.list = [self.val, ]

else:

self.list = [self.val, ] + self.suiv.list

"""

def ajoute_Tete(L, x):

return Noeud(x, L)

"""

def copyinstList(a):

b = repr(a).split()

return map(int, b)

import profile

profile.run('copyinstList(a)')

print '\n', copyinstList(a)

def copieIterative(z):

return z.list

v = copieIterative(a)

print v

"""

a = None

for _ in range(15) :

a = ajoute_Tete(a,randrange(1,1000,1))

b = None

for _ in range(6) :

b = ajoute_Tete(b,randrange(1,1000,1))

def copieIterative2(L):

a, b, alist = None, None, []

while L!= None:

a = ajoute_Tete(a, L.val)

alist, L = [L.val] + alist, L.suiv

for i in alist:

b = ajoute_Tete(b, i)

return b

def copieRecursive2(q):

while q != None:

return ajoute_Tete(copieRecursive2(q.suiv),q.val)

v = copieRecursive2(a)

z = copieIterative2(a)

print '\na =', a

print 'v = copieRecursive2(a) =', v

print 'z = copieIterative2(a) =', z

"""

# print "a.val =", a.val

# print "type(a) =", type(a)

if v == a:

print "IS equal"

else:

print "NOT equal"

"""

"""

def instToList (a):

b = repr(a).split()

return map(int, b)

def trier(a):

aList = instToList(a)

for s in range(len(aList)-1, 0, -1):

for i in range(s):

if aList[i] < aList[i + 1]:

aList[i], aList[i + 1] = aList[i + 1], aList[i]

b = None

for i in aList:

b = ajoute_Tete(b,i)

return b

"""

def trier(l):

l1 = l

while l1 != None:

if l1.suiv != None:

l2 = l1.suiv

while l2 != None:

if l2 < l1:

l1.val, l2.val = l2.val, l1.val

l2 = l2.suiv

l1 = l1.suiv

def fusionIter(m, n):

a = None

while m:

a = ajoute_Tete(a, m.val)

m = m.suiv

while n:

a = ajoute_Tete(a, n.val)

n = n.suiv

trier(a) # sorts instance a in place

return a

print '\nb =', b

w = fusionIter(a, b)

print '\nw = fusionIter(a, b) =', w