(线性表)在一个递增有序的线性表中,有数值相同的元素存在。若存储方式为单链表,设计算法去掉数值相同的元素,使表中不再有重复的元素
时间: 2023-05-23 15:06:15 浏览: 139
已知线性表中的元素以值递增有序排列,并以单链表作存储结构。试写一高效的算法,删除表中所有值相同的多余元素(使得操作后的线性表中所有元素的值均不相同)
A:
1. 首先遍历整个链表,对于每个节点,记录下其值和前一个节点的指针。
2. 对于第一个节点,没有前一个节点,故前一个节点的指针为空。
3. 对于每个非头节点,判断其值和前一个节点的值是否相同。
4. 如果相同,就将前一个节点的指针指向当前节点的下一个节点,然后删除当前节点。即将前一个节点的 next 指针指向当前节点的 next 指针所指向的节点。
5. 如果不相同,就继续遍历下一个节点。当遍历完成后,所有重复的节点均已被删除。
具体的实现可参考下面的代码:
```python
def remove_duplicate(node):
if node is None:
return node
prev, curr = None, node
seen = set()
while curr:
if curr.val in seen:
prev.next = curr.next
curr = None
else:
seen.add(curr.val)
prev = curr
curr = prev.next
return node
```
其中,prev 表示前一个节点,curr 表示当前节点,seen 用于记录已经遍历过的值。在遍历时,如果当前节点的值已经出现过,就删除当前节点。否则,将当前节点的值加入到 seen 中,继续向后遍历。最后将处理完的链表返回。
阅读全文