![\"\"](\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645012166470-Article_202.png\")
<\/p>\n<\/p>\n
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.<\/p>\n<\/p>\n
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.<\/p>\n
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.<\/p>\n
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.<\/p>\n
Let’s try to understand the problem with the help of examples:
\nIf the linked list given to us is (4,3)\u2192(7,3)\u2192(10,3)\u2192(10,4)\u2192(10,7)\u2192(10,8)\u2192NULL.<\/p>\n
![\"\"](\"https:\/\/prepbytes.com\/blog\/wp-content\/uploads\/2021\/10\/p_1-2.jpg\")
<\/p>\n
At this point, we have understood the problem statement. Now we will try to formulate an approach for this problem.<\/p>\n
Before moving to the approach section, try to think about how you can approach this problem.<\/p>\n
Let\u2019s move to the approach section.<\/p>\n
The approach is discussed in more depth in the algorithm section.<\/p>\n
1) Initialize two pointers prev<\/strong> and curr<\/strong> with the first and second node of the list, respectively.
\n2) Iterate the list till curr<\/strong> is not NULL.
\n3) If the x-coordinate of curr<\/strong>, as well as prev<\/strong>, is equal (i.e., vertical line), then:
\na) Create a start<\/strong> variable initialized to prev<\/strong>, which will denote the starting of the segment.
\nb) Move prev<\/strong> and curr<\/strong> forward by one node
\nc) Now, run a while loop until curr<\/strong> is not NULL and x-coordinates of curr<\/strong> and prev<\/strong> are equal.
\nd) Inside the loop, attach curr<\/strong> after start<\/strong> and delete the prev<\/strong> node.
\ne) Also, update prev<\/strong> to curr<\/strong> and move curr<\/strong> forward by one node.
\n4) If the y-coordinate of curr<\/strong>, as well as prev<\/strong>, is equal (i.e., Horizontal line), then:
\na) Create a start<\/strong> variable initialized to prev<\/strong>, which will denote starting of the segment.
\nb) Move prev<\/strong> and curr<\/strong> forward by one node.
\nc) Now, run a while loop until curr<\/strong> is not NULL and y-coordinates of curr<\/strong> and prev<\/strong> are equal.
\nd) Inside the loop, attach curr<\/strong> after start<\/strong> and delete the prev<\/strong> node.
\ne) Also, update prev<\/strong> to curr<\/strong> and move curr<\/strong> forward by one node.
\n5) If none of the two coordinates is equal, move forward prev<\/strong> and curr<\/strong> by one node.<\/p>\nDry Run<\/h3>\n
![\"\"](\"https:\/\/prepbytes.com\/blog\/wp-content\/uploads\/2021\/10\/p_2-2.jpg\")
\n![\"\"](\"https:\/\/prepbytes.com\/blog\/wp-content\/uploads\/2021\/10\/p_3-1.jpg\")
\n![\"\"](\"https:\/\/prepbytes.com\/blog\/wp-content\/uploads\/2021\/10\/p_4.jpg\")
<\/p>\nCode Implementation<\/h3>\n\t\t\t\t\t\t