Remove middle points of linked list having each node containing coordinates of x,y plane.

0 votes
asked in Interview Question by kumar

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)
Output: Linked List should be changed to following
Add question to:

1 Answer

+1 vote
answered by aqs
selected by admin
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 is None:
    return root

  previous = root
  current =
  previous_slope = get_slope(current, previous)
  while is not None:
    new_slope = get_slope(, current)

    if new_slope == previous_slope: =
      current =
      previous = current
      current =

  return root


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