# Remove middle points in a linked list of line segments

Table of Contents

## 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;
}```