链表快排

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

def qsort(start, end):
    if start == end:
        return 
    pivot = start.val
    p = start
    q = start.next
    #count = 1
    while(q != end):
        if q.val < pivot:
            p = p.next
            # p一直记录小于pivot的最后一个位置
            p.val, q.val = q.val, p.val
        q = q.next
        #print('count: ', count)
        count += 1
    start.val, p.val = p.val, start.val
    qsort(start, p)
    qsort(p.next, end)

link = [3,6,4,6,3,9,0,12,13,53,1,12,34]
head = ListNode(link[0])

p = head
for i in range(1, len(link)):
    p.next = ListNode(link[i])
    p = p.next

end = p.next
qsort(head, end)
while head:
    print(head.val, end=' ')
    head = head.next

### output:
0 1 3 3 4 6 6 9 12 12 13 34 53