Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x. You should preserve the original relative order of the nodes in each of the two partitions. Example:
Input: head = 1->4->3->2->5->2, x = 3 Output: 1->2->2->4->3->5
Para resolver a questão, temos que ordenar pelos seguintes críterios, em ordem de prioridade:
- Valores menores que
xprimeiro. - Valores mais à esquerda na lista original primeiro.
Isso é, precisamos fazer uma lista de prioridade com que armazene tuplas do tipo:
t = (critério 1, critério 2, valor)
Para o critério 1 podemos fazer dois grupos (0 e 1), um para valores menores que x e outro para o restante.
Para o critério 2 podemos usar o índice dos elementos na lista original.
Ao final da construção da fila, podemos fazer uma lista encadeada com o terceiro item de cada tupla.
Primeiramente declaramos a fila de prioridade:
pqueue = []Depois precisamos percorrer a lista de entrada e colocar os elementos na fila, conforme os critérios estabelecidos:
current = head
i = 0
while(current != None):
val = current.val
heappush(pqueue, (0 if val < x else 1, i, val))
current = current.next
i += 1Agora construímos a nova lista de adjacência e retornamos:
newhead = ListNode(heappop(pqueue)[2])
current = newhead
while(len(pqueue) > 0):
current.next = ListNode(heappop(pqueue)[2])
current = current.next
return newheadTomando cuidado, no começo, com o caso da lista vazia:
if(head == None):
return headViu algum erro? mande um email para pabloemanuell2017@gmail.com