算法设计题(要求同上):head指向一单链表,请编写算法在单链表中每个data域为S的结点前插入一个data域为T的新结点。
时间: 2024-10-07 22:01:55 浏览: 11
这个问题可以使用迭代或递归的方式来解决。这里提供一种简单的迭代解法:
1. 首先,创建一个新的节点`new_node`,它的`data`字段设置为`T`。
2. 初始化两个指针,`current`指向链表的头节点,`prev`初始化为`None`。
3. 当`current`不是`None`且其`data`字段不等于`S`时,继续遍历:
- 将`new_node`的`next`指向`current`,即把新节点插入到当前节点之前。
- 更新`prev`为`current`,`current`为`current.next`。
4. 当找到第一个`data`字段为`S`的节点时(即`current`),将`prev`的`next`设为`new_node`,然后`prev`和`new_node`都移动到下一个节点。
5. 如果遍历结束还没有找到`S`,说明链表中不存在`S`,直接让`new_node`的`next`为原链表的头节点即可。
```python
def insert_between(head, T, S):
new_node = Node(T) # 创建新节点
current = head
prev = None
while current is not None and current.data != S:
prev = current
current = current.next
if current is None: # 如果链表中不存在S,则在头节点后插入
new_node.next = head
return new_node
prev.next = new_node
new_node.next = current
return head # 返回新的链表头节点
```
在这个算法中,我们假设已经有一个Node类,其中包含数据`data`和指向下一个节点的指针`next`。