Dada una lista enlazada de coordenadas donde los puntos adyacentes forman una línea vertical o una línea horizontal. Elimine puntos de la lista vinculada que se encuentran en medio de una línea horizontal o vertical.
Ejemplos:
Input: (0,10)->(1,10)->(5,10)->(7,10)
|
(7,5)->(20,5)->(40,5)
Output: Linked List should be changed to following
(0,10)->(7,10)
|
(7,5)->(40,5)
The given linked list represents a horizontal line from (0,10)
to (7, 10) followed by a vertical line from (7, 10) to (7, 5),
followed by a horizontal line from (7, 5) to (40, 5).
Input: (2,3)->(4,3)->(6,3)->(10,3)->(12,3)
Output: Linked List should be changed to following
(2,3)->(12,3)
There is only one vertical line, so all middle points are removed.
Fuente: experiencia de entrevista de Microsoft
La idea es realizar un seguimiento del Node actual, el siguiente Node y el siguiente-siguiente Node. Si bien el siguiente Node es el mismo que el siguiente, siga eliminando el siguiente Node. En este procedimiento completo, debemos vigilar el cambio de punteros y verificar los valores NULL.
Las siguientes son implementaciones de la idea anterior.
Python
# Python program to remove middle points in a linked list of
# line segments,
class LinkedList(object):
def __init__(self):
self.head = None
# Linked list Node
class Node(object):
def __init__(self, x, y):
self.x = x
self.y = y
self.next = None
# This function deletes middle nodes in a sequence of
# horizontal and vertical line segments represented
# by linked list.
def deleteMiddle(self):
# If only one node or no node...Return back
if self.head == None or self.head.next == None or self.head.next.next == None:
return self.head
Next = self.head.next
NextNext = Next.next
# check if this is vertical or horizontal line
if self.head.x == Next.x:
# Find middle nodes with same value as x and
# delete them.
while NextNext != None and Next.x == NextNext.x:
self.head.next = Next.next
Next.next = None
# Update NextNext for the next iteration
Next = NextNext
NextNext = NextNext.next
elif self.head.y == Next.y:
# find middle nodes with same value as y and
# delete them
while NextNext != None and Next.y == NextNext.y:
self.head.next = Next.next
Next.next = None
# Update NextNext for the next iteration
Next = NextNext
NextNext = NextNext.next
else:
# Adjacent points should have same x or same y
print "Given list is not valid"
return None
# recur for other segment
# temporarily store the head and move head forward.
temp = self.head
self.head = self.head.next
# call deleteMiddle() for next segment
self.deleteMiddle()
# restore head
self.head = temp
# return the head
return self.head
# Given a reference (pointer to pointer) to the head
# of a list and an int, push a new node on the front
# of the list.
def push(self, x, y):
# 1 & 2: Allocate the Node &
# Put in the data
new_node = self.Node(x, y)
# 3. Make next of new Node as head
new_node.next = self.head
# 4. Move the head to point to new Node
self.head = new_node
def printList(self):
temp = self.head
while temp != None:
print "(" + str(temp.x) + "," + str(temp.y) + ")->",
temp = temp.next
print ''
# Driver program
llist = LinkedList()
llist.push(40,5)
llist.push(20,5)
llist.push(10,5)
llist.push(10,8)
llist.push(10,10)
llist.push(3,10)
llist.push(1,10)
llist.push(0,10)
print "Given list"
llist.printList()
if llist.deleteMiddle() != None:
print "Modified Linked List is"
llist.printList()
# This code is contributed by BHAVYA JAIN
Producción:
Given Linked List: (0,10)-> (1,10)-> (3,10)-> (10,10)-> (10,8)-> (10,5)-> (20,5)-> (40,5)-> Modified Linked List: (0,10)-> (10,10)-> (10,5)-> (40,5)->
La complejidad temporal de la solución anterior es O(n) donde n es un número de Nodes en la lista enlazada dada.
Ejercicio:
El código anterior es recursivo, escriba un código iterativo para el mismo problema. Consulte a continuación la solución.
Enfoque iterativo para eliminar los puntos medios en una lista enlazada de segmentos de línea
Consulte el artículo completo sobre Dada una lista enlazada de segmentos de línea, elimine los puntos medios 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