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 <stdio.h>
#include <stdlib.h>
// Node has 3 fields including x, y
// coordinates and a pointer to next
// node
struct Node
{
int x, y;
struct Node *next;
};
/* Function to insert a node at
the beginning */
void push(struct Node ** head_ref,
int x,int y)
{
struct Node* new_node =
(struct Node*) malloc(sizeof(struct 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(struct Node *head)
{
struct Node *temp = head;
while (temp != NULL)
{
printf("(%d,%d)-> ",
temp->x, temp->y);
temp = temp->next;
}
printf("");
}
// Utility function to remove Next from
// linked list and link nodes after it
// to head
void deleteNode(struct Node *head,
struct 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.
struct Node* deleteMiddle(struct Node *head)
{
// If only one node or no node...
// Return back
if (head == NULL || head->next == NULL ||
head->next->next == NULL)
return head;
struct Node* Next = head->next;
struct 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()
{
struct 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);
printf("Given Linked List: ");
printList(head);
if (deleteMiddle(head) != NULL);
{
printf("Modified Linked List: ");
printList(head);
}
return 0;
}
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