# Given a linked list of line segments, remove middle points ### Introduction

The linked list is one of the most important concepts to know while preparing for interviews. Having a good grasp of a linked list can be a huge plus point in coding interviews.

### Problem Statement

In this problem, we will be given a linked list, where each node will have two integers representing the x and y coordinates of a point. We need to remove the middle points present in the line segments drawn by joining the coordinates of the node.

### Problem Statement Understanding

The problem statement is quite straightforward; we have to draw line segments corresponding to the coordinates of the nodes and then remove the middle points present in each line segment.

Suppose we have a horizontal line segment formed by 6 different points, then according to the problem statement, we need to remove the four points in between the starting and ending point of the line segment and leave the starting and ending point as it is.

• We need to do the same with the lines that are vertical i.e., leave starting and ending points and remove middle points.

Let’s try to understand the problem with the help of examples:
If the linked list given to us is (4,3)→(7,3)→(10,3)→(10,4)→(10,7)→(10,8)→NULL. • From the above graphical plot of the given linked list, we see that the first three nodes form a line segment parallel to the x-axis.
• So, the middle point in the line segment is the second node. Hence, it is removed.
• Similarly, the last three nodes form a line segment parallel to the y-axis and the last second node, and the last third node, are the points that lie in between the starting and ending point of the segment.
• Hence, both of them are removed from the list (removing middle points from line segment).
• So, after removing all the middle points from the linked list, our final resultant linked list will be: (4,3)→(10,3)→(10,8)→NULL

At this point, we have understood the problem statement. Now we will try to formulate an approach for this problem.

Before moving to the approach section, try to think about how you can approach this problem.

• If stuck, no problem, we will thoroughly see how we can approach this problem in the next section.

Let’s move to the approach section.

### Approach

• We will maintain two pointers initialized by the first and second nodes of the given list, respectively.
• Now, we will iterate the list, and while iterating, we will check if two consecutive nodes have the same x or y coordinate or not.
• If that is the case, then we will remove all the nodes that have the same x or y coordinate as the first pointer and keep the second pointer at the end of the segment.
• In this way, all the middle points of the line segments will be removed, and hence our objective will be satisfied.

The approach is discussed in more depth in the algorithm section.

### Algorithm

1) Initialize two pointers prev and curr with the first and second node of the list, respectively.
2) Iterate the list till curr is not NULL.
3) If the x-coordinate of curr, as well as prev, is equal (i.e., vertical line), then:
a) Create a start variable initialized to prev, which will denote the starting of the segment.
b) Move prev and curr forward by one node
c) Now, run a while loop until curr is not NULL and x-coordinates of curr and prev are equal.
d) Inside the loop, attach curr after start and delete the prev node.
e) Also, update prev to curr and move curr forward by one node.
4) If the y-coordinate of curr, as well as prev, is equal (i.e., Horizontal line), then:
a) Create a start variable initialized to prev, which will denote starting of the segment.
b) Move prev and curr forward by one node.
c) Now, run a while loop until curr is not NULL and y-coordinates of curr and prev are equal.
d) Inside the loop, attach curr after start and delete the prev node.
e) Also, update prev to curr and move curr forward by one node.
5) If none of the two coordinates is equal, move forward prev and curr by one node.

### Dry Run   ### Code Implementation

```#include
using namespace std;

class Node {
public:
int x, y;
Node *next;
//constructor
Node(int x,int y){
this->x = x;
this->y = y;
next = NULL;
}
};

// Using this function we will print the list
{
while (temp != NULL) {
printf("(%d, %d)-> ", temp->x, temp->y);
temp = temp->next;
}
printf("NULL\n");
}

// Using these functions we will delete the middle nodes from the given linked list.
{

while (curr) {

// x-coordinate equality check
if (curr->x == prev->x)
{
Node *start = prev;
prev = curr;
curr = curr->next;

//remove the nodes in middle of
//the segment parallel to y-axis
while (curr && curr->x == prev->x)
{
start->next = curr;
free(prev);
prev = curr;
curr = curr->next;
}
}

// y-coordinate equality check
else if (curr->y == prev->y)
{
Node *start = prev;
prev = curr;
curr = curr->next;

//remove the nodes in middle of
//the segment parallel to x-axis
while (curr && curr->y == prev->y)
{
start->next = curr;
free(prev);
prev = curr;
curr = curr->next;
}
} else {
prev = curr;
curr = curr->next;
}
}
}

int main() {

return 0;
}
```
```#include
#include

struct Node
{
int x, y;
struct Node *next;
};

void push(struct Node ** head_ref, int x,int y)
{
struct Node* new_node =
(struct Node*) malloc(sizeof(struct Node));
new_node->x  = x;
new_node->y  = y;
}

{
while (temp != NULL)
{
printf("(%d,%d)-> ", temp->x,temp->y);
temp = temp->next;
}
printf("\n");

}

void deleteNode(struct Node *head, struct Node *Next)
{
Next->next = NULL;
free(Next);
}

{
// If only one node or no node...Return back

struct Node *NextNext = Next->next ;

// Check if this is a vertical line or horizontal line
{
// Find middle nodes with same x value, and delete them
while (NextNext !=NULL && Next->x==NextNext->x)
{

// 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)
{

// 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

}

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

{
}
return 0;
}

```
```class LineSegment
{
class Node
{
int x,y;
Node next;
Node(int x, int y)
{
this.x = x;
this.y = y;
next = null;
}
}

/* This function deletes middle nodes in a sequence of
horizontal and vertical line segments represented
Node deleteMiddle()
{
// If only one node or no node...Return back

Node NextNext = Next.next;

// check if this is vertical or horizontal line
{
// Find middle nodes with same value as x and
// delete them.
while (NextNext != null && Next.x == NextNext.x)
{
Next.next = null;

// Update NextNext for the next iteration
Next = NextNext;
NextNext = NextNext.next;
}
}

// if horizontal
{
// find middle nodes with same value as y and
// delete them
while (NextNext != null && Next.y == NextNext.y)
{
Next.next = null;

// Update NextNext for the next iteration
Next = NextNext;
NextNext = NextNext.next;
}
}
// Adjacent points should have same x or same y
else
{
System.out.println("Given list is not valid");
return null;
}

// call deleteMiddle() for next segment
this.deleteMiddle();

}
void push(int x, int y)
{
Node new_node = new Node(x,y);
}
void printList()
{
while (temp != null)
{
System.out.print("("+temp.x+","+temp.y+")->");
temp = temp.next;
}
System.out.println("NULL");
}

/* Driver program to test above functions */
public static void main(String args[])
{
LineSegment llist = new LineSegment();

llist.push(4,3);
llist.push(7,3);
llist.push(10,3);
llist.push(10,4);
llist.push(10,7);
llist.push(10,8);

System.out.println("Given list");
llist.printList();

if (llist.deleteMiddle() != null)
{
llist.printList();
}
}
}

```
```class LinkedList(object):
def __init__(self):

class Node(object):
def __init__(self, x, y):
self.x = x
self.y = y
self.next = None

def deleteMiddle(self):
while curr:

if curr.x == prev.x:

start = prev
prev = curr
curr = curr.next

while curr and curr.x == prev.x:
start.next = curr
del prev
prev = curr
curr = curr.next

elif curr.y == prev.y:

start = prev
prev = curr
curr = curr.next

while curr and curr.y == prev.y:
start.next = curr
del prev
prev = curr
curr = curr.next

else:
prev = curr
curr = curr.next

def push(self, x, y):

new_node = self.Node(x, y)

def printList(self):
while temp != None:
print ("(" + str(temp.x) + "," + str(temp.y) + ")->",end=" ")
temp = temp.next
print ("Null")

# Driver program
llist.push(10,8)
llist.push(10,7)
llist.push(10,4)
llist.push(10,3)
llist.push(7,3)
llist.push(4,3)

print ("Given list")
llist.printList()

llist.deleteMiddle()
llist.printList()

```