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.
C++
// C++ program to remove intermediate points
// in a linked list that represents horizontal
// and vertical line segments
#include <bits/stdc++.h>
using namespace std;
// Node has 3 fields including x, y
// coordinates and a pointer
// to next node
class Node
{
public:
int x, y;
Node *next;
};
/* Function to insert a node
at the beginning */
void push(Node ** head_ref,
int x,int y)
{
Node* new_node =new Node();
new_node->x = x;
new_node->y = y;
new_node->next = (*head_ref);
(*head_ref) = new_node;
}
/* Utility function to print
a singly linked list */
void printList(Node *head)
{
Node *temp = head;
while (temp != NULL)
{
cout << "(" << temp->x <<
"," << temp->y << ")-> ";
temp = temp->next;
}
cout << endl;
}
// Utility function to remove Next
// from linked list and link nodes
// after it to head
void deleteNode(Node *head,
Node *Next)
{
head->next = Next->next;
Next->next = NULL;
free(Next);
}
// This function deletes middle nodes
// in a sequence of horizontal and
// vertical line segments represented
// by linked list.
Node* deleteMiddle(Node *head)
{
// 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 a vertical line
// or horizontal line
if (head->x == Next->x)
{
// Find middle nodes with same x
// value, and delete them
while (NextNext != NULL &&
Next->x == NextNext->x)
{
deleteNode(head, Next);
// Update Next and NextNext
// for next iteration
Next = NextNext;
NextNext = NextNext->next;
}
}
// If horizontal line
else if (head->y == Next->y)
{
// Find middle nodes with same y
// value, and delete them
while (NextNext != NULL &&
Next->y == NextNext->y)
{
deleteNode(head, Next);
// Update Next and NextNext for
// next iteration
Next = NextNext;
NextNext = NextNext->next;
}
}
// Adjacent points must have either
// same x or same y
else
{
puts("Given linked list is not valid");
return NULL;
}
// Recur for next segment
deleteMiddle(head->next);
return head;
}
// Driver code
int main()
{
Node *head = NULL;
push(&head, 40,5);
push(&head, 20,5);
push(&head, 10,5);
push(&head, 10,8);
push(&head, 10,10);
push(&head, 3,10);
push(&head, 1,10);
push(&head, 0,10);
cout << "Given Linked List: ";
printList(head);
if (deleteMiddle(head) != NULL);
{
cout << "Modified Linked List: ";
printList(head);
}
return 0;
}
// This is code is contributed by rathbhupendra
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