708 Insert into a Cyclic Sorted List

Python

最简单思路，首先一个while循环找到最大值和最小值，第二个while循环将元素插到合适的位置中。注意特殊情况，就是插在链表最后端的时候。

"""
# Definition for a Node.
class Node(object):
    def __init__(self, val, next):
        self.val = val
        self.next = next
"""
class Solution(object):
    def insert(self, head, insertVal):
        """
        :type head: Node
        :type insertVal: int
        :rtype: Node
        """
        newNode = ListNode(insertVal)

        if head is None:
            newNode.next = newNode
            return newNode
        minVal = head.val
        maxVal = head.val
        prev, curr = head, head.next
        while curr != head:
            if minVal > curr.val:
                minVal = curr.val
            if maxVal < curr.val:
                maxVal = curr.val
            curr = curr.next
        prev, curr = head, head.next
        while curr:
            if insertVal <= curr.val and insertVal >= prev.val:
                prev.next = newNode
                newNode.next = curr
                return head
            if curr.val == minVal and prev.val == maxVal:
                if insertVal >= maxVal or insertVal <= minVal:
                    prev.next = newNode
                    newNode.next = curr
                    return head
            prev = curr
            curr = curr.next