708. 循环有序列表的插入
Difficulty
Medium
Tags
链表
Star
给定循环单调非递减列表中的一个点，写一个函数向这个列表中插入一个新元素 insertVal ，使这个列表仍然是循环非降序的。
给定的可以是这个列表中任意一个顶点的指针，并不一定是这个列表中最小元素的指针。
如果有多个满足条件的插入位置，你可以选择任意一个位置插入新的值，插入后整个列表仍然保持有序。
如果列表为空（给定的节点是 null），你需要创建一个循环有序列表并返回这个节点。否则。请返回原先给定的节点。
示例 1：
输入：head = [3,4,1], insertVal = 2
输出：[3,4,1,2]
解释：在上图中，有一个包含三个元素的循环有序列表，你获得值为 3 的节点的指针，我们需要向表中插入元素 2 。新插入的节点应该在 1 和 3 之间，插入之后，整个列表如上图所示，最后返回节点 3 。
示例 2：
输入：head = [], insertVal = 1
输出：[1]
解释：列表为空（给定的节点是 null），创建一个循环有序列表并返回这个节点。
示例 3：
输入：head = [1], insertVal = 0
输出：[1,0]
法1
思路
三种情况：
- 头节点为空：
- 头节点和插入值相同：直接插入head后面
- 找链表中值最大的节点 和 小于插入值节点中最大的节点
题解
""" # 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: 'Optional[Node]', insertVal: int) -> 'Node': res = head # 保存一下头节点 new_node = Node(insertVal) # 头节点为空 if head is None: new_node = Node(insertVal) new_node.next = new_node return new_node # 和头节点值相同 elif head.val == insertVal: insert_node = head # 找 链表中最大的节点，和比当前值小的节点中最大的节点 else: max_node = None # 找到比 insertval 小的最大节点 max_max_node = head while head: if ((head.val < insertVal) and (max_node is None or head.val >= max_node.val)): max_node = head # 找最大的节点 if head.val > max_max_node.val: max_max_node = head head = head.next if head is res: break if max_node: insert_node = max_node else: insert_node = max_max_node # 执行插入操作 nxt = insert_node.next insert_node.next = new_node new_node.next = nxt return res
""" # 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: 'Optional[Node]', insertVal: int) -> 'Node': if head is None: new_node = Node(insertVal) new_node.next = new_node return new_node cur = head max_node = None insert_node = None while cur: if cur.val < insertVal: if insert_node is None or insert_node.val <= cur.val: insert_node = cur if max_node is None or max_node.val < cur.val: max_node = cur cur = cur.next if cur is head: break if insert_node is None: insert_node = max_node new_node = Node(insertVal) new_node.next = insert_node.next insert_node.next = new_node return head