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.
Java
// Java program to remove middle points in
// a linked list of line segments,
class LinkedList
{
// Head of list
Node head;
// Linked list Node
class Node
{
int x,y;
Node next;
Node(int x, int y)
{
this.x = x;
this.y = y;
next = null;
}
}
// This function deletes middle nodes
// in a sequence of horizontal and
// vertical line segments represented
// by linked list.
Node deleteMiddle()
{
// If only one node or no node...
// Return back
if (head == null ||
head.next == null ||
head.next.next == null)
return head;
Node Next = head.next;
Node NextNext = Next.next;
// Check if this is vertical or
// horizontal line
if (head.x == Next.x)
{
// Find middle nodes with same value
// as x and delete them.
while (NextNext != null &&
Next.x == NextNext.x)
{
head.next = Next.next;
Next.next = null;
// Update NextNext for the next iteration
Next = NextNext;
NextNext = NextNext.next;
}
}
// if horizontal
else if (head.y == Next.y)
{
// find middle nodes with same value as y and
// delete them
while (NextNext != null && Next.y == NextNext.y)
{
head.next = Next.next;
Next.next = null;
// Update NextNext for the next iteration
Next = NextNext;
NextNext = NextNext.next;
}
}
// Adjacent points should have same x or same y
else
{
System.out.println("Given list is not valid");
return null;
}
// recur for other segment
// temporarily store the head and move head forward.
Node temp = head;
head = head.next;
// call deleteMiddle() for next segment
this.deleteMiddle();
// restore head
head = temp;
// return the head
return 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. */
void push(int x, int y)
{
/* 1 & 2: Allocate the Node &
Put in the data*/
Node new_node = new Node(x,y);
/* 3. Make next of new Node as head */
new_node.next = head;
/* 4. Move the head to point to new Node */
head = new_node;
}
void printList()
{
Node temp = head;
while (temp != null)
{
System.out.print("("+temp.x+","+temp.y+")->");
temp = temp.next;
}
System.out.println();
}
/* Driver program to test above functions */
public static void main(String args[])
{
LinkedList llist = new 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);
System.out.println("Given list");
llist.printList();
if (llist.deleteMiddle() != null)
{
System.out.println("Modified Linked List is");
llist.printList();
}
}
} /* This code is contributed by Rajat Mishra */
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