设计一个算法,删除带头结点的单链表L中第 i 个结点,同时释放被删结点的空间,成功操作返回true,否则返回false。(须定义单链表结点类型)
时间: 2024-09-25 10:02:44 浏览: 38
深入二叉树两个结点的最低共同父结点的详解
设计这样一个算法,首先我们需要定义单链表节点类型,通常包括两个字段:数据元素和指向下一个节点的指针。假设我们已经有一个链表头节点`head`和一个整数`i`作为删除位置。
```python
# 定义单链表节点
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def delete_node(head: ListNode, i: int) -> bool:
# 如果链表为空或 i 越界
if not head or i <= 0:
return False
# 处理普通情况,从第二个节点开始遍历,找到第 i - 1 个节点
current = head
previous = None
for _ in range(i - 1):
if not current:
return False
previous = current
current = current.next
# 删除当前节点,将前一个节点的next指向前一个节点的下一个节点
if current:
previous.next = current.next
# 释放当前节点空间
current = None # 或者在这里添加释放内存的操作,取决于具体的内存管理机制
return True
```
在这个函数中,如果能正确找到第 i 个节点并删除它,就会返回 `True`;否则,如遇到空链表、无效的位置等,会返回 `False`。注意,这个函数不会直接处理头节点的情况,因为它默认的是从头节点后的第 i 个节点开始查找。如果需要删除头节点,可以在函数开头额外检查 `i == 1` 的条件,并相应地处理。
阅读全文