写一个函数用来建立非递减有序链表,并解释每一行的作用
时间: 2023-06-26 10:08:48 浏览: 33
下面是一个用来建立非递减有序链表的 Python 函数:
```python
def build_sorted_list(nums: List[int]) -> ListNode:
dummy = ListNode(float('-inf')) # 创建一个虚拟头结点
pre = dummy # 初始化前驱结点为虚拟头结点
for num in nums:
while pre.next and pre.next.val < num: # 找到插入位置
pre = pre.next
new_node = ListNode(num) # 创建新结点
new_node.next = pre.next # 插入新结点
pre.next = new_node
pre = dummy # 恢复前驱结点为虚拟头结点
return dummy.next # 返回非虚拟头结点
```
每行代码的作用如下:
1. `def build_sorted_list(nums: List[int]) -> ListNode:`:定义一个函数,接收一个整数列表作为输入参数,并返回一个链表结点。
2. `dummy = ListNode(float('-inf'))`:创建一个值为负无穷的虚拟头结点,用于连接真正的链表头结点。
3. `pre = dummy`:初始化前驱结点为虚拟头结点。
4. `for num in nums:`:遍历整数列表中的每一个数字。
5. `while pre.next and pre.next.val < num:`:寻找插入位置,直到链表末尾或者找到一个大于等于当前数字的结点。
6. `new_node = ListNode(num)`:创建一个新的链表结点,其值为当前数字。
7. `new_node.next = pre.next`:将新结点插入到前驱结点和后继结点之间。
8. `pre.next = new_node`:更新前驱结点的后继结点为新结点。
9. `pre = dummy`:恢复前驱结点为虚拟头结点。
10. `return dummy.next`:返回真正的链表头结点,即虚拟头结点的后继结点。