Given a linked list with each node containing coordinates of x,y plane. Remove middle points.

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)

Login

+1 vote

Best answer

Here is the general idea:

- keep parsing the linked list

- when the slope (horizontal/vertical) doesn’t change from previous value ignore the middle element.

Here is the pseudo code:

```
def get_slope(Node a, Node b): // returns 'vertical' or 'horiozntal'
def remove_internal_points(Node root):
if root is None or root.next is None:
return root
previous = root
current = root.next
previous_slope = get_slope(current, previous)
while current.next is not None:
new_slope = get_slope(current.next, current)
if new_slope == previous_slope:
previous.next = current.next
current = current.next
else:
previous = current
current = current.next
return root
```

commented
by
admin

your solution is correct, It would be better if you can provide full working code.

- All categories
- Interview Question (230)
- Coding(Hiring) (42)
- Competitive Coding (5)
- Phone Interview (5)
- Written Test (15)
- Algorithm (12)
- Puzzle (4)

...