【Leetcode Daily】LCR029循环有序列表的插入

题目浅析

• 想查看原题可以点击题目链接。

• 简单地说，就是给一个循环链表，链表内的数值按非降序排列，现在给一个要插入的值，返回插完后的链表头。

思路分享

• 根据分析，就三种情况，一是能找到处于两个一小一大节点中间（升序），二和三就是插入值是最大值或最小值，对于后面两种，先要找到整个链表的边界点，也就是唯一没有按升序的地方，插到这里就行。

  https://leetcode.cn/problems/4ueAj6/solutions/1/gan-jue-da-jia-xie-de-du-you-dian-fu-za-k1klz/

代码解答（强烈建议自行解答后再看）

• 参考题解

"""
# Definition for a Node.
class Node:
    def __init__(self, val=None, next=None):
        self.val = val
        self.next = next
"""

class Solution:
    def insert(self, head: 'Node', insertVal: int) -> 'Node':
        if not head:
            head = Node(insertVal)
            head.next = head
            return head
        
        cur = head
        while cur.next != head:
            if cur.next.val < cur.val:
                if cur.next.val >= insertVal:
                    # 插入的是最小值
                    break
                elif cur.val <= insertVal:
                    # 插入的是最大值
                    break
            # 处理中间情况
            if cur.val <= insertVal <= cur.next.val:
                break
            cur = cur.next
        cur.next = Node(insertVal, cur.next)
        return head