编写函数从一个链表中删除元素值为x和y的之间所有节点
时间: 2024-04-30 11:22:49 浏览: 100
以下是Python语言的示例代码:
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def delete_between(head: ListNode, x: int, y: int) -> ListNode:
# 处理链表头部
while head and head.val >= x and head.val <= y:
head = head.next
# 处理链表中间部分
curr = head
while curr and curr.next:
if curr.next.val >= x and curr.next.val <= y:
curr.next = curr.next.next
else:
curr = curr.next
return head
```
其中,我们定义了一个`ListNode`类来表示链表节点,每个节点包含一个`val`属性表示节点值和一个`next`属性表示指向下一个节点的指针。
`delete_between`函数接收一个链表头节点`head`和两个整数`x`、`y`,表示需要删除的节点值的范围。函数首先处理头部,将值在范围内的节点全部删除,然后处理链表中间部分,从头节点开始遍历链表,如果发现下一个节点的值在范围内,就将当前节点的`next`属性指向下一个节点的`next`属性,从而删除下一个节点。最后返回删除后的链表头节点。
这个函数的时间复杂度为$O(n)$,其中$n$是链表节点数。
阅读全文