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

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

相关问题

在一个递增有序的线性表中，有数值相同的元素存在。若存储方式为单链表，设计算法去掉数值相同的元素，使表中不再有重复的元素。例如（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指向链表的末尾，算法结束。

设计一算法,在数据元素有序的顺序存储结构的线性表中插入一个值为x的操作

设计一个算法，在数据元素有序的顺序存储结构的线性表中插入一个值为x的操作。

1. 首先，遍历线性表，找到第一个大于等于x的元素的位置。我们可以使用一个指针来记录当前遍历到的位置，如果当前元素小于x，则指针向后移动一位，直到找到第一个大于等于x的元素的位置。

2. 在找到的位置插入x，将该位置后面的元素依次后移一位。我们可以从线性表的末尾开始，将每个元素向后移动一位，直到插入位置。

3. 将x插入到找到的位置。我们可以直接将x赋值给该位置，完成插入操作。

以下是伪代码实现：

procedure InsertElement(L, x)
i <- 0 // 初始化指针i为0
while i < length(L) and L[i] < x do // 寻找插入位置
i <- i + 1
end while
for j <- length(L) - 1 to i do // 后移元素
L[j+1] <- L[j]
end for
L[i] <- x // 插入元素x
end procedure

这个算法的时间复杂度为O(n)，其中n为线性表的长度。这是因为要遍历线性表寻找插入位置，然后进行元素后移操作，最后插入元素x。