Leetcode 885 Solution

class Node(object):
    def __init__(self, pos, next):
        self.pos = pos
        self.next = next


class ExamRoom(object):

    def __init__(self, N):
        """
        :type N: int
        """
        self.head = Node(None, None)
        self.N = N


    def seat(self):
        """
        :rtype: int
        """
        if self.head.next is None:
            self.head.next = Node(0, None)
            return 0

        node = self.head.next
        left_dist = node.pos
        right_dist = sys.maxint

        best_dist = 0
        best_node = None

        while node:
            if node.next:
                if best_dist < (node.next.pos - node.pos) / 2:
                    best_dist = (node.next.pos - node.pos) / 2
                    best_node = node
                node = node.next
            else:
                right_dist = self.N - 1 - node.pos
                break

        if left_dist >= best_dist and left_dist >= right_dist:
            self.head.next = Node(0, self.head.next)
            return 0
        elif best_dist > left_dist and best_dist >= right_dist:
            best_node.next = Node(best_node.pos + best_dist, best_node.next)
            return best_node.pos + best_dist
        else:
            node.next = Node(self.N - 1, None)
            return self.N - 1


    def leave(self, p):
        """
        :type p: int
        :rtype: None
        """
        prev = self.head
        node = self.head.next

        while node:
            if node.pos == p:
                prev.next = node.next
                break

            prev = node
            node = node.next


# Your ExamRoom object will be instantiated and called as such:
# obj = ExamRoom(N)
# param_1 = obj.seat()
# obj.leave(p)