[LeetCode]Insert into a Cyclic Sorted List

思路很直观，注意edge case，大概有以下几种情况：

1. list为空，我们新建node，并且将next指向自身
2. 如果insertVal在某处节点curr满足，curr->val <= insertVal <= curr->next->val，insertVal插入curr之后
3. 如果2中的情况没有出现，说明当前插入值是新的最大/最小值，我们需要在当前最大值对应的节点(有多个的话选最靠后的一个)之后插入

按照以上三种情况处理即可，时间复杂度O(N)，代码如下：

	class Solution {
	public:
	Node* insert(Node* head, int insertVal) {
	if (!head)
	{
	Node* node = new Node(insertVal, nullptr);
	node->next = node;
	return node;
	}
	Node* curr = head, *maxNode = head;
	bool inserted = false;
	while(true)
	{
	if (curr->next->val < curr->val)
	maxNode = curr;
	if (curr->next->val >= insertVal && curr->val <= insertVal)
	{
	Node* node = new Node(insertVal, curr->next);
	curr->next = node;
	inserted = true;
	break;
	}
	curr = curr->next;
	if (curr == head)break;
	}
	//turning point from max to min
	if (!inserted)
	{
	Node* node = new Node(insertVal, maxNode->next);
	maxNode->next = node;
	}
	return head;
	}
	};

view raw Insert into a Cyclic Sorted List.cpp hosted with ❤ by GitHub