对于不带头结点的单链表L,设计一个递归算法删除第一个值为x的结点。
时间: 2023-11-27 12:51:57 浏览: 98
下面是递归算法的实现:
```python
def delete_node(head, x):
if head is None:
# 如果链表为空,则直接返回空链表
return None
elif head.val == x:
# 如果头结点的值等于x,直接删除头结点并返回剩余链表
return head.next
else:
# 如果头结点的值不等于x,则从剩余的链表中删除x结点
head.next = delete_node(head.next, x)
return head
```
使用方法如下:
```python
# 定义链表结点类
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
# 创建链表 1 -> 2 -> 3 -> 2 -> 4
head = ListNode(1, ListNode(2, ListNode(3, ListNode(2, ListNode(4)))))
# 删除值为2的结点
head = delete_node(head, 2)
# 打印剩余链表
while head:
print(head.val, end=" ")
head = head.next
```
输出结果为:
```
1 3 4
```
需要注意的是,由于本算法使用了递归,因此对于较长的链表可能会导致栈溢出的问题。因此在实际使用时需要注意链表的长度。
阅读全文