# Remove middle points in a linked list of line segments

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

//O(1) constant time
}

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
{
//single or double LL return
{
}
struct LLNode *NextOfNext = Next->next ;
//Points are on horizantal line
{
while (NextOfNext !=NULL && Next->y==NextOfNext->y)
{
//delete middle nodes(Next)
Next->next = NULL;
free(Next);
//Continue Iteration
Next = NextOfNext;
NextOfNext = NextOfNext->next;
}
}
//Points are on vertical line
{
while (NextOfNext !=NULL && Next->x==NextOfNext->x)
{
//delete middle nodes(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
}

// Driver program to tsst above functions
int main()
{