## In the given linked list each node consists of co-ordinates (pair of data). These co-ordinates are either from vertical line or horizontal line. We need to delete all the points from the linked list which are in the middle of a line.

### Example

**Time complexity : O(n)**

## Algorithm

**a.** Store a pair of data (x, y) in each node.

**b.** Traverse in the linked list, keep track of current node, next node and next-next node.

**c.** If x or y value of current, next and next-next are equal then delete next.

**d.** Do this until any of current, next and next-next is not null.

**e.** If adjacent points doesn`t have either same x or same y,then print invalid input.

## C++ Program

#include <bits/stdc++.h> using namespace std; struct LLNode { int x, y; struct LLNode* next; }; /* Function to insertAtBeginning a node */ void insertAtBeginning(struct LLNode** head, int x,int y) { struct LLNode* curr = new LLNode; curr->x = x; curr->y = y; curr->next = NULL; if(*head == NULL) *head=curr; //if this is first node make this as head of list else { curr->next=*head; //else make the curr (new) node's next point to head and make this new node a the head *head=curr; } //O(1) constant time } //display linked list void display(struct LLNode**node) { struct LLNode *temp= *node; while(temp!=NULL) { if(temp->next!=NULL) cout<<"("<<temp->x<<", "<<temp->y<<")"<<"->"; else cout<<"("<<temp->x<<", "<<temp->y<<")"; temp=temp->next; //move to next node } //O(number of nodes) cout<<endl; } //function to delete middle nodes struct LLNode* DeleteMiddleNodes(struct LLNode *head) { //single or double LL return if (head==NULL || head->next ==NULL || head->next->next==NULL) { return head; } struct LLNode* Next = head->next; struct LLNode *NextOfNext = Next->next ; //Points are on horizantal line if (head->y==Next->y) { while (NextOfNext !=NULL && Next->y==NextOfNext->y) { //delete middle nodes(Next) head->next = Next->next; Next->next = NULL; free(Next); //Continue Iteration Next = NextOfNext; NextOfNext = NextOfNext->next; } } //Points are on vertical line else if (head->x == Next->x) { while (NextOfNext !=NULL && Next->x==NextOfNext->x) { //delete middle nodes(Next) head->next = Next->next; Next->next = NULL; free(Next); //Continue Iteration Next = NextOfNext; NextOfNext = NextOfNext->next; } } //adjacent points without same x or same y else { cout<<"Invalid Input:"<<endl; return NULL; } //Recurtion DeleteMiddleNodes(head->next); return head; } // Driver program to tsst above functions int main() { struct LLNode *head = NULL; insertAtBeginning(&head,15,21); insertAtBeginning(&head,15,18); insertAtBeginning(&head,15,11); insertAtBeginning(&head,15,9); insertAtBeginning(&head,13,9); insertAtBeginning(&head,13,7); insertAtBeginning(&head,13,3); insertAtBeginning(&head,13,1); cout<<"Input linked list is:"; display(&head); if(DeleteMiddleNodes(head)!=NULL); { cout<<"\nOutput linked list is: "; display(&head); } return 0; }