已知递增有序的单链表A,编写算法实现向A中插入或删除一个元素,并保持A的有序性。
时间: 2024-10-18 08:09:37 浏览: 40
JAVA单链表的简单操作(递增单链表插入数据,链表逆置,链表逆序合成)
要在已知递增有序的单链表A中插入或删除一个元素并保持其有序性,你可以采用以下策略:
1. 插入操作:
- 如果新元素小于链表中的第一个元素,则将新元素作为新的头节点,更新头指针。
- 否则,遍历链表,找到第一个大于等于新元素的位置。将当前节点与其前驱节点链接起来,然后将新元素指向当前节点。
```python
def insert_sorted_node(head, value):
if not head or value < head.val:
new_node = ListNode(value)
new_node.next = head
return new_node
else:
current = head
while current.next and current.next.val < value:
current = current.next
new_node = ListNode(value)
new_node.next = current.next
current.next = new_node
```
2. 删除操作:
- 如果要删除的值等于头节点,直接更新头指针指向下一个节点(如果存在的话)。
- 遍历链表,当找到目标值时,将其前驱节点的next指针设置为当前节点的下一个节点。
```python
def delete_sorted_node(head, value):
if head is not None and head.val == value:
head = head.next
return head
current = head
prev = None
while current is not None and current.val != value:
prev = current
current = current.next
if current is not None:
prev.next = current.next
```
阅读全文