Python 已知由一个线性链表表示的线性表中含有3类字符的数据元素(如:字母、数字和其他字符),试编写算法将该线性链表分割为3个循环链表,其中每个循环链表表示的线性表中均只含有一类字符。
时间: 2023-05-30 14:05:10 浏览: 143
把链表中字符、数字和其他符号分开
算法思路:
1. 定义3个空的循环链表,分别表示字母、数字和其他字符的线性表;
2. 遍历原始线性链表,根据数据元素的类型将其添加到对应的循环链表中;
3. 将每个循环链表的尾节点指向头节点,形成循环链表。
算法实现:
```python
class Node:
def __init__(self, data=None):
self.data = data
self.next = None
def split_list(head):
# 定义3个空的循环链表
alpha_head = alpha_tail = Node()
digit_head = digit_tail = Node()
other_head = other_tail = Node()
# 遍历原始线性链表,根据数据元素的类型将其添加到对应的循环链表中
p = head.next
while p:
if p.data.isalpha():
alpha_tail.next = p
alpha_tail = p
elif p.data.isdigit():
digit_tail.next = p
digit_tail = p
else:
other_tail.next = p
other_tail = p
p = p.next
# 将每个循环链表的尾节点指向头节点,形成循环链表
alpha_tail.next = alpha_head.next
digit_tail.next = digit_head.next
other_tail.next = other_head.next
return alpha_head, digit_head, other_head
```
算法解释:
该算法使用了3个指针分别表示字母、数字和其他字符的循环链表的尾节点。遍历原始线性链表时,根据数据元素的类型将其添加到对应的循环链表中,并更新对应的循环链表的尾节点指针。最后将每个循环链表的尾节点指向头节点,形成循环链表。
阅读全文