单链表是升序排列,将值为x的结点插入head的表头
时间: 2024-05-15 22:15:02 浏览: 15
以下是Python代码实现:
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def insertNode(head: ListNode, x: int) -> ListNode:
new_node = ListNode(x) # 创建新节点
# 处理空链表的情况
if not head:
return new_node
# 处理头节点为x的情况
if head.val == x:
new_node.next = head
return new_node
# 处理头节点大于x的情况
if head.val > x:
new_node.next = head
return new_node
# 处理头节点小于x的情况
cur = head
while cur.next and cur.next.val < x:
cur = cur.next
new_node.next = cur.next
cur.next = new_node
return head
```
可以先判断链表是否为空,为空则直接将新节点作为头节点返回。
然后判断头节点是否为x,如果是,则将新节点插入头节点前面并返回。
如果头节点大于x,则将新节点插入头节点前面并返回。
如果头节点小于x,则从头节点开始遍历链表,直到找到第一个大于等于x的节点或到达链表尾部。然后将新节点插入到该节点前面并返回头节点。
时间复杂度为O(n),其中n为链表的长度。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)