Dada una lista enlazada individualmente con cada Node que tiene un puntero «arbitrario» adicional que actualmente apunta a NULL. Necesita hacer que el puntero «arbitrario» apunte al siguiente Node de mayor valor.
Recomendamos encarecidamente minimizar su navegador e intentarlo usted mismo primero.
Una solución simple es atravesar todos los Nodes uno por uno, para cada Node, encontrar el Node que tiene el siguiente valor mayor del Node actual y cambiar el puntero siguiente. La complejidad temporal de esta solución es O(n 2 ).
Una solución eficiente funciona en tiempo O(nLogn). La idea es usar Merge Sort para lista enlazada .
1) Atraviese la lista de entrada y copie el siguiente puntero en el puntero de arbitraje para cada Node.
2) Haga Merge Sort para la lista enlazada formada por punteros arbitrales.
A continuación se muestra la implementación de la idea anterior. Todas las funciones de clasificación de fusión se toman de aquí . Las funciones tomadas se modifican aquí para que funcionen en punteros de arbitraje en lugar de punteros siguientes.
Python3
# Python3 program to populate arbit pointers
# to next higher value using merge sort
head = None
# Link l node
class Node:
def __init__(self, data):
self.data = data
self.next = None
self.arbit = None
# Utility function to print result
# linked l
def printList(node, anode):
print("Traversal using Next Pointer")
while (node != None):
print(node.data, end = ", ")
node = node.next
print("Traversal using Arbit Pointer");
while (anode != None):
print(anode.data, end = ", ")
anode = anode.arbit
# This function populates arbit pointer in
# every node to the next higher value. And
# returns pointer to the node with minimum
# value
def populateArbit(start):
temp = start
# Copy next pointers to arbit pointers
while (temp != None):
temp.arbit = temp.next
temp = temp.next
# Do merge sort for arbitrary pointers and
# return head of arbitrary pointer linked l
return MergeSort(start)
# Sorts the linked l formed by arbit pointers
# (does not change next pointer or data)
def MergeSort(start):
# Base case -- length 0 or 1
if (start == None or start.arbit == None):
return start
# Split head into 'middle' and
# 'nextofmiddle' sublists
middle = getMiddle(start)
nextofmiddle = middle.arbit
middle.arbit = None
# Recursively sort the sublists
left = MergeSort(start)
right = MergeSort(nextofmiddle)
# answer = merge the two sorted lists together
sortedlist = SortedMerge(left, right)
return sortedlist
# Utility function to get the
# middle of the linked l
def getMiddle(source):
# Base case
if (source == None):
return source
fastptr = source.arbit
slowptr = source
# Move fastptr by two and slow ptr by one
# Finally slowptr will point to middle node
while (fastptr != None):
fastptr = fastptr.arbit
if (fastptr != None):
slowptr = slowptr.arbit
fastptr = fastptr.arbit
return slowptr
def SortedMerge(a, b):
result = None
# Base cases
if (a == None):
return b
elif (b == None):
return a
# Pick either a or b, and recur
if (a.data <= b.data):
result = a
result.arbit = SortedMerge(a.arbit, b)
else:
result = b
result.arbit = SortedMerge(a, b.arbit)
return result
# Driver code
if __name__=='__main__':
# Let us create the l shown above
head = Node(5)
head.next = Node(10)
head.next.next = Node(2)
head.next.next.next = Node(3)
# Sort the above created Linked List
ahead = populateArbit(head)
print("Result Linked List is:")
printList(head, ahead)
# This code is contributed by rutvik_56
Producción:
Result Linked List is: Traversal using Next Pointer 5, 10, 2, 3, Traversal using Arbit Pointer 2, 3, 5, 10,
Consulte el artículo completo sobre Apuntar al siguiente Node de mayor valor en una lista vinculada con un puntero arbitrario para obtener más detalles.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA