Linked-list natural merge sort in Python

Question

I implemented the linked-list natural merge sort in Python, and I referred to this awesome if not poetic gist and this implementation in Go. Here is my code:

# Linked list is either empty or a value and a link to the next list
empty = None # empty list
class LL(object):
 __slots__ = "value", "next"
 def __init__(self, value, next=empty):
 self.value = value
 self.next = next
 def __le__(self, other):
 return self.value <= other.value
 def __lt__(self, other):
 return self.value < other.value
def reverse(head, size=-1):
 """
 reference: https://stackoverflow.com/a/22049871/3552
 """
 new_head = None
 while head:
 temp = head
 head = temp.next
 temp.next = new_head
 new_head = temp
 size-=1
 if not size:
 tail = new_head
 while tail.next:
 tail = tail.next
 tail.next = head
 return new_head
 return new_head
def find_next_stop(head):
 if head is empty:
 return head, 0, empty
 next_node = head.next
 if next_node is empty:
 return head, 1, empty
 size = 2
 if head <= next_node:
 while(next_node.next and next_node <= next_node.next):
 size += 1
 next_node = next_node.next
 next_node = next_node.next
 else:
 while(next_node.next and next_node.next < next_node):
 size += 1
 next_node = next_node.next
 next_node = next_node.next
 head = reverse(head, size)
 return head, size, next_node
def linked_list_natural_merge_sort(head):
 """Revising from mergesort-linkedlist to Natural_mergesort_linkedlist [1].
 [1]: https://gist.github.com/zed/5651186
 """
 while True:
 p = head
 head, tail = empty, empty 
 nmerges = 0 
 while p is not empty:
 nmerges += 1 
 q = p 
 p, psize, next_start, = find_next_stop(p)
 q, qsize, next_start = find_next_stop(next_start)
 while psize > 0 or (qsize > 0 and q is not empty):
 if psize == 0: 
 e, q = q, q.next 
 qsize -= 1
 elif qsize == 0 or q is empty:
 e, p = p, p.next 
 psize -= 1
 elif p.value <= q.value: 
 e, p = p, p.next
 psize -= 1
 else: # p.value > q.value i.e., first element of q is lower
 e, q = q, q.next
 qsize -= 1
 # add e to the end of the output list
 if tail is not empty:
 tail.next = e
 else: 
 head = e # smallest item among two lists
 tail = e
 p = next_start
 if tail is not empty:
 tail.next = empty
 # if we have done only one merge, we're finished
 if nmerges <= 1: 
 return head
def mklist(initializer):
 it = reversed(initializer)
 try:
 x = next(it)
 except StopIteration:
 return empty 
 else:
 head = LL(x)
 for value in it:
 head = LL(value, head)
 return head
def walk(head, size=-1):
 while head is not empty:
 if size:
 size -= 1
 else:
 break
 yield head.value
 head = head.next
def tolist(head, size=-1):
 return list(walk(head, size))

I tested it as follows:

def test():
 for n, r, k in product(range(10), repeat=3):
 L = list(range(n)) + [n//2]*r + [n-1]*k
 random.shuffle(L)
 head = mklist(L)
 assert tolist(head) == L
 head = linked_list_natural_merge_sort(head)
 assert tolist(head) == sorted(L)
if __name__ == "__main__":
 import random
 from itertools import product
 test()

After reading this answer I modified the linked_list_natural_merge_sort function as follows:

def linked_list_natural_merge_sort(head):
 """Revising from mergesort-linkedlist to Natural_mergesort_linkedlist [1].
 [1]: https://gist.github.com/zed/5651186
 """
 p = q = head
 psize = 0
 tail = empty
 while q is not empty:
 tail = empty
 q, qsize, next_q = find_next_stop(q)
 msize = psize + qsize
 while qsize > 0 or psize > 0:
 if psize == 0:
 e, q = q, q.next
 qsize -= 1
 elif qsize == 0:
 e, p = p, p.next
 psize -= 1
 elif p <= q:
 e, p = p, p.next
 psize -= 1
 else:
 e, q = q, q.next
 qsize -= 1
 if tail is empty:
 head = e
 else:
 tail.next = e
 tail = e
 psize = msize
 q = next_q
 p = head
 if tail is not empty:
 tail.next = empty
 return head

Any suggestions or recommendations for further improvements will be highly appreciated. The complete code can be found here.