LC.708。循環ソートリストに挿入

Lc 708 Insert Into Cyclic Sorted List

class Node(object): def __init__(self, val, next): self.val = val self.next = next class Solution(object): def insert(self, head, insertVal): ''' corner case: 1) When the elements are not all the same: 1. The inserted value is a maximum or minimum value, which should be inserted at the place where the first and the last 2. The inserted value is a general value, just insert it 2) The elements are all the same, just insert them anywhere ''' insertNode = Node(insertVal, head) if not head: return insertNode isSame = True pNode = head.next while pNode != head: if pNode.val != head.val: isSame = False break pNode = pNode.next if isSame: insertNode.next = pNode.next pNode.next = insertNode else: pNode = head while True: if pNode.val <= insertVal <= pNode.next.val or (pNode.val > pNode.next.val and (insertVal >= pNode.val or insertVal <= pNode.next.val)): insertNode.next = pNode.next pNode.next = insertNode break else: pNode = pNode.next return head class Solution1(object): def insert(self, head, insertVal): ''' Method 2 one pass When the pNode points to the head again, it means that there is no insertion point in the ring, that is, the elements in the ring are the same ''' pNode = head insertNode = Node(insertVal, None) if not head: return insertNode while True: if pNode.val <= insertVal <= pNode.next.val or (pNode.val > pNode.next.val and (insertVal >= pNode.val or insertVal < pNode.next.val)): break if pNode.next == head: break pNode = pNode.next insertNode.next = pNode.next pNode.next = insertNode return head