Write a Python function to implement the quick sort algorithm over a singly linked list. The input of your function should be a reference pointing to the first node of a linked list, and the output of your function should also be a reference to the first node of a linked list, in which the data have been sorted into the ascending order. You may use the LinkedQueue class in your program.

 

class ListQueue: default_capacity = 5 definit__(self): self._data= [None] *ListQueue. default_capacity self._size = 0 self._front = 0 self._end 0 deflen (self): return self._ _size def is empty (self): return self.__size ==0 def first (self): if self. is_empty(): else: print (Queue is empty.') return self.__data[self.__front] def dequeue (self): if self. is_empty(): print (Queue is empty. return None answer = self. _data[self.__front] self. data[self. front] = None self._front = (self.____front+1) \ self.__size -=1 return answer % ListQueue. default_capacity def enqueue (self, e): if self._size == ListQueue. default_capacity: print (The queue is full.') return None self.__data[self.__end] = e self._end = (self._end+1) \ % ListQueue. default_capacity self.__size = 1 def outputQ (self): print (self.__data)