InterviewSolution
Saved Bookmarks
InterviewSolution
| 1. |
A linked list of coordinates is given, with neighboring points forming either a vertical or horizontal line. Remove points in between the starting and ending points of the horizontal or vertical line from the linked list. |
|
Answer» The objective is to KEEP track of the current node, the next node, and the node after that. Continue deleting the next node when it is the same as the next-next node. We must keep a watch on the shifting of pointers and check for NULL values throughout the entire procedure. Time Complexity is O(n). Implementation: VOID deleteNode(Node *head, Node *t){ head->next = t->next; t->next = NULL; free(t);}// This function deletes the intermediate nodes in a sequence of// horizontal and vertical line segments represented by a// linked list.Node* deleteMiddleNodes(Node *head){ if (head == NULL || head->next == NULL || head->next->next == NULL) return head; Node* t = head->next; Node *tt = t->next; // Check whether this is a vertical line or horizontal line if (t->y == head->y) { // Find intermediate nodes with same y value, and delete them while (tt != NULL && t->y == tt->y) { deleteNode(head, t); // UPDATE t and tt for the next iteration t = tt; tt = tt->next; } } // check for vertical line else if (t->x == head->x) { // Find intermediate nodes with same x value, and delete them while (tt != NULL && t->x == tt->x) { deleteNode(head, t); // Update t and tt for the next iteration t = tt; tt = tt->next; } } // Adjacent points must EITHER have same x or same y else { cout<<"GIVEN linked list is not valid"; return NULL; } // Recursion for the next segment deleteMiddleNodes(head->next); return head;} |
|