标签: 链表
难度: Medium
Submission
运行时间: 24 ms
内存: 0.0 MB
"""
# 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 head is None:
res = Node(insertVal)
res.next = res
return res
node = Node(insertVal)
min_node = head
max_node = head
p = head.next
prev = head
flag = False
while p is not head:
if p.val >= max_node.val:
max_node = p
if p.val < min_node.val:
min_node = p
if prev.val <= insertVal and p.val >= insertVal:
node.next = p
prev.next = node
return head
prev = p
p = p.next
if prev.val <= insertVal and p.val >= insertVal:
node.next = p
prev.next = node
else:
node.next = min_node
max_node.next = node
return head
Explain
这个题解的思路是遍历循环链表，找到合适的插入位置。具体来说： 1. 如果链表为空，则新建一个节点，让它的 next 指向自己，构成循环链表。 2. 遍历链表，同时记录最大值节点和最小值节点。 3. 在遍历过程中，如果当前节点的值小于等于要插入的值，且下一个节点的值大于等于要插入的值，那么就在这两个节点之间插入新节点。 4. 如果遍历完一圈没有找到合适的插入位置，说明要插入的值是最大值或最小值，此时插入到最大值节点之后即可。
时间复杂度: O(n)
空间复杂度: O(1)
class Solution:
def insert(self, head: 'Node', insertVal: int) -> 'Node':
# 如果链表为空，新建一个节点，让它的 next 指向自己，构成循环链表
if head is None:
res = Node(insertVal)
res.next = res
return res
# 新建要插入的节点
node = Node(insertVal)
# 初始化最小值节点和最大值节点为 head
min_node = head
max_node = head
# p 指向 head 的下一个节点
p = head.next
# prev 指向 head
prev = head
# 遍历链表
while p is not head:
# 更新最大值节点
if p.val >= max_node.val:
max_node = p
# 更新最小值节点
if p.val < min_node.val:
min_node = p
# 如果找到合适的插入位置，则插入新节点并返回 head
if prev.val <= insertVal and p.val >= insertVal:
node.next = p
prev.next = node
return head
# 移动 prev 和 p
prev = p
p = p.next
# 如果遍历完一圈没找到合适的插入位置，则插入到最大值节点之后
if prev.val <= insertVal and p.val >= insertVal:
node.next = p
prev.next = node
else:
node.next = min_node
max_node.next = node
return head
Explore
在处理循环链表时，可以通过设置一个起始点，并在遍历过程中检查当前遍历到的节点是否重新回到了起始点来确保不会无限循环。在本题解中，起始点是头节点`head`，遍历过程中使用了一个指针`p`，从`head.next`开始遍历，并检查`p`是否再次等于`head`来判断是否完成了一圈的遍历。这样可以保证即使是循环链表，也只会遍历一圈，避免了无限循环的情况。
选择在最大值节点之后插入的原因是为了保持链表的有序性和简化插入逻辑。在循环有序链表中，最大值节点的下一个节点自然是最小值节点。因此，插入到最大值节点之后自动地意味着插入到了最小值节点之前。这样做不仅维持了链表的循环特性，也简化了判断，无需额外操作就可以处理值位于链表值范围之外的情况。
在循环链表中，插入新节点并不改变头节点`head`的位置，除非特别指定。头节点是链表的入口点，而循环链表的特性保证了无论从哪个节点开始，都能遍历整个链表。因此，即使插入新的节点，只要链表的结构保持完整，返回原始的头节点仍然可以访问整个链表，不需要重新定位头节点。
若所有链表中的节点值相同，新插入的节点值也相同，根据题解的逻辑，在遍历链表时，将无法找到一个严格符合`prev.val <= insertVal and p.val >= insertVal`的位置，因为所有值都相等。因此，遍历将完成一整圈并返回到起始点。在此情况下，根据题解的最后的处理，新节点将被插入到最大值节点之后，即任意位置（因为所有节点值相同，任意节点都可以视为最大或最小）。