题目要求建立一个有n个元素的一维数 组,并创建一个有序单链表,最小时间复杂度。
时间: 2023-06-12 07:04:34 浏览: 238
建立一个单链表
可以使用链表插入排序来创建有序单链表,时间复杂度为 O(n^2)。具体步骤如下:
1. 创建一个空的有序单链表。
2. 遍历一维数组,依次将每个元素插入到有序单链表中。
3. 对于每个元素,从链表的头结点开始遍历,找到第一个比它大的节点的前一个节点,然后将该元素插入到该节点后面。
4. 如果链表中没有比它大的节点,则将该元素插入到链表的尾部。
5. 最终得到的链表就是有序的单链表。
代码示例:
```python
class Node:
def __init__(self, val):
self.val = val
self.next = None
def insert_sort(nums):
dummy = Node(0)
for num in nums:
cur = dummy
while cur.next and cur.next.val < num:
cur = cur.next
new_node = Node(num)
new_node.next = cur.next
cur.next = new_node
return dummy.next
# 示例
nums = [3, 2, 1, 5, 4]
head = insert_sort(nums)
while head:
print(head.val)
head = head.next
```
输出结果为:
```
1
2
3
4
5
```
阅读全文