已知单链表L是一个递增有序表,试编写一高效算法,删除表中值大于min且小于max的结点(若表中有这样的结点),同时释放被删除结点的空间,这里min和max是两个给定的参数。请分析算法的时间复杂度。
时间: 2024-03-07 16:47:38 浏览: 138
单链表常考算法及代码
4星 · 用户满意度95%
针对这个问题,可以采取如下的算法步骤:
1. 先处理特殊情况,如果L为空或者L中所有结点的值都小于等于min或大于等于max,则不需要进行删除操作,直接返回L即可。
2. 使用两个指针p和q遍历链表L,p指向当前结点,q指向p的前一个结点。如果p结点的值大于min且小于max,则将p结点从链表中摘除,并释放p的空间。否则,p和q两个指针向后移动一个结点。
3. 最后返回链表L即可。
算法的时间复杂度为O(n),其中n为链表L的长度。因为每个结点最多被访问两次,一次是遍历到它本身,一次是它被删除。因此,时间复杂度为线性的。
以下是Python代码实现:
```python
def delete_nodes_in_range(L, min_val, max_val):
if not L or L.val > max_val or L.val >= min_val:
return L
dummy = ListNode(0)
dummy.next = L
p = L
q = dummy
while p:
if p.val > min_val and p.val < max_val:
q.next = p.next
del p
p = q.next
else:
p = p.next
q = q.next
return dummy.next
```
阅读全文