在一个递增有序的线性表中，有数值相同的元素存在。若存储方式为单链表，设计算法去掉数值相同的元素，使表中不再有重复的元素。例如（7，10，10，21，30，42，42，42，51，70）将变作（7，10，21，30，42，51，70）

可以使用双指针法，一个指针p指向当前节点，另一个指针q指向p的下一个节点。如果p节点的值等于q节点的值，则将q节点删除，即将p的next指向q的next，然后q指向p的下一个节点，继续比较。如果p节点的值不等于q节点的值，则将p指向q，q指向p的下一个节点，继续比较。直到q指向链表的末尾，算法结束。

相关问题

（线性表）在一个递增有序的线性表中，有数值相同的元素存在。若存储方式为单链表，设计算法去掉数值相同的元素，使表中不再有重复的元素

A：

1. 首先遍历整个链表，对于每个节点，记录下其值和前一个节点的指针。

2. 对于第一个节点，没有前一个节点，故前一个节点的指针为空。

3. 对于每个非头节点，判断其值和前一个节点的值是否相同。

4. 如果相同，就将前一个节点的指针指向当前节点的下一个节点，然后删除当前节点。即将前一个节点的 next 指针指向当前节点的 next 指针所指向的节点。

5. 如果不相同，就继续遍历下一个节点。当遍历完成后，所有重复的节点均已被删除。

具体的实现可参考下面的代码：

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 中，继续向后遍历。最后将处理完的链表返回。

在一个递增有序的线性表『中，有数值相同的元素存在。 若存储方式为单链表，设计算法去掉数值相同的元素，使表中不再有重复的元素

在单链表中去除重复元素并保持递增顺序，可以采用迭代的方式来实现。这里是一种简单的算法步骤：

1. 定义两个指针，`current` 和 `previous`，初始时都指向头节点。
2. 循环遍历链表，直到链表结束：
a. 检查 `current` 节点的值是否等于 `previous` 节点的值。如果不同，则将 `previous` 指向 `current`，然后移动 `previous` 到下一个节点。
b. 如果 `current` 的值等于 `previous` 的值，说明这是一个重复节点。不做任何操作，直接将 `current` 移动到下一个节点。
3. 当循环结束后，`previous` 就会停在最后一个非重复节点之后，这时你可以将链表的尾部设置为 `previous`，它指向的就是新的末尾。

算法伪代码如下：

while current != null:
    if current.value == previous.value:
        current = current.next
    else:
        previous.next = current
        previous = current
    current = current.next

if current != null:
    previous.next = None  # 设置新尾部