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

Translate ยป