Insert into a Cyclic Sorted List

Given a node from a cyclic linked list which has been sorted, write a function to insert a value into the list such that it remains a cyclic sorted list. The given node can be any single node in the list. Return the inserted new node.

Notice

3->5->1is a cyclic list, so3is next node of1. 3->5->1is same with5->1->3

Example

Given a list, and insert a value4: 3->5->1 Return5->1->3->4

几种情况

1) Linked List is empty:  

2) New node is to be inserted just before the head node:    

3) New node is to be  inserted somewhere after the head: 
4) Linked List 只有一个node

"""
Definition of ListNode
class ListNode(object):

    def __init__(self, val, next=None):
        self.val = val
        self.next = next
"""
class Solution:
    # @param {ListNode} node a list node in the list
    # @param {int} x an integer
    # @return {ListNode} the inserted new list node
    def insert(self, node, x):
        # Write your code here
        #  case1: linkedlist is empty
        if not node:
            node = ListNode(x)
            node.next = node
            return node
        prev = None
        p = node
        newNode = ListNode(x)
        while True:
            prev = p
            p=p.next
            # case2:x值在pre和p中间
            if newNode.val >= prev.val and newNode.val <= p.val:
                break
            # case3: x值在head node前边，也就是pre>p的时候
            if (prev.val > p.val) and (newNode.val >= prev.val or newNode.val <= p.val):
                break
            # case4: 如果linkedlist只有一个node的情况
            if p is node:
                break
        prev.next = newNode
        newNode.next = p
        return newNode