1、有一个整数单链表 L设计一个算法删除其中所有值为x的结点并给出算法的时间和空间复杂度。例如L=12231x=2删除后 L=131。

算法思路：

1. 遍历链表，找到第一个值为 x 的结点，记为 pre。

2. 再从 pre 的下一个结点开始遍历，如果遇到值为 x 的结点，就删除它。

3. 重复步骤 2，直到链表末尾。

4. 对于第一个结点的处理，需要特殊考虑。

时间复杂度：O(n)，其中 n 是链表的长度。因为每个结点最多被访问两次，一次是在找到它的时候，一次是在删除它的时候。

空间复杂度：O(1)，只需要几个辅助变量。

算法实现：

def delete_x(L, x):
    # 处理第一个结点
    while L is not None and L.val == x:
        L = L.next
    if L is None:
        return None
    pre, cur = L, L.next
    while cur is not None:
        if cur.val == x:
            pre.next = cur.next
            cur = cur.next
        else:
            pre, cur = cur, cur.next
    return L

测试代码：

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

def print_list(L):
    while L is not None:
        print(L.val, end=' ')
        L = L.next
    print()

def create_list(arr):
    if not arr:
        return None
    head = ListNode(arr[0])
    p = head
    for x in arr[1:]:
        node = ListNode(x)
        p.next = node
        p = node
    return head

arr = [1, 2, 2, 3, 1]
L = create_list(arr)
print_list(L)
L = delete_x(L, 2)
print_list(L)

输出结果：

1 2 2 3 1 
1 3 1