Home » Interview Questions » LinkedList Interview Questions » Remove middle points in a linked list of line segments

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

READ  Find Nth Node

How useful was this post?

Click on a star to rate it!

Average rating / 5. Vote Count

No votes so far! Be the first to rate this post.

As you found this post useful...

Follow us on social media!

We are sorry that this post was not useful for you!

Let us improve this post!

Tell us how we can improve this post?

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions