单链表有序性插入
时间: 2023-07-26 10:03:35 浏览: 38
单链表的有序性插入可以按照以下步骤进行:
1. 遍历单链表,找到待插入节点的位置。
2. 将待插入节点的 next 指针指向该位置原来节点的 next 指针所指的节点。
3. 将该位置原来节点的 next 指针指向待插入节点。
下面是一个示例代码:
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def insert_node(head: ListNode, val: int) -> ListNode:
new_node = ListNode(val)
if not head:
return new_node
if val < head.val:
new_node.next = head
return new_node
cur = head
while cur.next and cur.next.val < val:
cur = cur.next
new_node.next = cur.next
cur.next = new_node
return head
```
其中,head 表示单链表的头节点,val 表示待插入节点的值。在遍历单链表时,若待插入节点的值小于当前节点的值,则将待插入节点插入到当前节点之前即可。若遍历完整个单链表都没找到合适的位置,则将待插入节点插入到单链表的末尾。