编写算法删除单链表中所有值为x的结点,构造测试用例进行测试
时间: 2024-09-26 12:03:16 浏览: 36
当你需要从单链表中删除所有值为x的节点时,可以采用迭代或递归的方式来实现这个操作。这里是一个简单的迭代算法:
```python
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
def remove_elements(head, x):
dummy = ListNode(0) # 创建虚拟头节点
dummy.next = head
prev = dummy
curr = head
while curr:
if curr.val == x:
prev.next = curr.next
else:
prev = curr
curr = curr.next
return dummy.next
```
在这个函数中,我们遍历链表,如果当前节点值等于x,则跳过它;否则更新prev指向下一个节点,然后继续检查下一个节点。
下面是一些测试用例:
```python
# 测试用例1: 空链表
head = None
result = remove_elements(head, 5)
assert result is None
# 测试用例2: 链表只有一个元素,且值为x
head = ListNode(5)
result = remove_elements(head, 5)
assert result is None
# 测试用例3: 链表有多个连续的x节点
head = ListNode(1)
head.next = ListNode(5)
head.next.next = ListNode(5)
head.next.next.next = ListNode(6)
result = remove_elements(head, 5)
assert result.val == 6
assert result.next is None
# 测试用例4: 链表中有其他值的节点,x不在其中
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(5)
head.next.next.next = ListNode(3)
result = remove_elements(head, 5)
assert result.next.next.val == 3
```
阅读全文