Given a linked list of line segments, remove middle points - GeeksforGeeks
Read full article from Given a linked list of line segments, remove middle points - GeeksforGeeks
Given a linked list of co-ordinates where adjacent points either form a vertical line or a horizontal line. Delete points from the linked list which are in the middle of a horizontal or vertical line.
Input: (0,10)->(1,10)->(5,10)->(7,10)
|
(7,5)->(20,5)->(40,5)
Output: Linked List should be changed to following
(0,10)->(7,10)
|
(7,5)->(40,5)
The given linked list represents a horizontal line from (0,10)
to (7, 10) followed by a vertical line from (7, 10) to (7, 5),
followed by a horizontal line from (7, 5) to (40, 5).
Input: (2,3)->(4,3)->(6,3)->(10,3)->(12,3)
Output: Linked List should be changed to following
(2,3)->(12,3)
There is only one vertical line, so all middle points are removed.
The idea is to keep track of current node, next node and next-next node. While the next node is same as next-next node, keep deleting the next node. In this complete procedure we need to keep an eye on shifting of pointers and checking for NULL values.
struct node* deleteMiddle(struct node *head){ // If only one node or no node...Return back if (head==NULL || head->next ==NULL || head->next->next==NULL) return head; struct node* Next = head->next; struct node *NextNext = Next->next ; // Check if this is a vertical line or horizontal line if (head->x == Next->x) { // Find middle nodes with same x value, and delete them while (NextNext !=NULL && Next->x==NextNext->x) { deleteNode(head, Next); // Update Next and NextNext for next iteration Next = NextNext; NextNext = NextNext->next; } } else if (head->y==Next->y) // If horizontal line { // Find middle nodes with same y value, and delete them while (NextNext !=NULL && Next->y==NextNext->y) { deleteNode(head, Next); // Update Next and NextNext for next iteration Next = NextNext; NextNext = NextNext->next; } } else // Adjacent points must have either same x or same y { puts("Given linked list is not valid"); return NULL; } // Recur for next segment deleteMiddle(head->next); return head;}
The above code is recursive, write an iterative code for the same problem.
void deleteNode(struct node *head, struct node *Next)
{
head->next = Next->next;
Next->next = NULL;
free(Next);
}
void deleteMiddle(node *head)
{
while(head!=NULL && head->next!=NULL && head->next->next!=NULL)
{
node *p=head;
node *q=head->next;
node *r=head->next->next;
if(p->x== q->x && p->x==r->x)
{
p->next=r;
delete q;
}
else if(p->y== q->y && p->y==r->y)
{
p->next=r;
delete q;
}
else
head=head->next;
}
}
