有一个线性表(a1，a2，…，an)，其中n≥2，采用带头结点的单链表存储，头指针为L，现查找某个元素值等于x的结点指针，若不存在这样的结点返回NULL。分别写出下面3种情况的查找语句。要求时间尽量少。

1. 顺序查找：

// 顺序查找元素值等于x的结点，返回结点指针，若不存在返回NULL
Node* search(Node* L, int x) {
    Node* p = L->next; // p指向第一个结点
    while (p != NULL) {
        if (p->data == x) {
            return p; // 找到了，返回结点指针
        }
        p = p->next; // 继续向后遍历
    }
    return NULL; // 找不到，返回NULL
}

2. 优化的顺序查找：

如果我们知道要查找的元素可能出现在链表的前面几个结点，就可以采用优化的顺序查找，将这些结点放在前面。这样就可以减少遍历的次数，提高查找效率。

// 优化的顺序查找元素值等于x的结点，返回结点指针，若不存在返回NULL
Node* search(Node* L, int x) {
    Node* p = L->next; // p指向第一个结点
    Node* pre = L; // pre指向p的前驱结点
    while (p != NULL) {
        if (p->data == x) {
            // 将p结点移到链表头部
            pre->next = p->next;
            p->next = L->next;
            L->next = p;
            return p; // 找到了，返回结点指针
        }
        pre = p; // pre指向p
        p = p->next; // 继续向后遍历
    }
    return NULL; // 找不到，返回NULL
}

3. 折半查找：

如果链表是有序的，可以采用折半查找，每次将查找范围缩小一半，直到找到或者找不到为止。

// 折半查找元素值等于x的结点，返回结点指针，若不存在返回NULL
Node* search(Node* L, int x) {
    Node* p = L->next; // p指向第一个结点
    Node* q = L->next; // q指向最后一个结点
    int len = 0; // 链表长度
    while (q != NULL) {
        len++;
        q = q->next; // 统计链表长度，并将q指向最后一个结点
    }
    int low = 1; // 查找范围的下界
    int high = len; // 查找范围的上界
    while (low <= high) {
        int mid = (low + high) / 2; // 计算中间位置
        p = L->next; // 重新将p指向第一个结点
        for (int i = 1; i < mid; i++) {
            p = p->next; // 将p指向中间位置的结点
        }
        if (p->data == x) {
            return p; // 找到了，返回结点指针
        }
        else if (p->data < x) {
            low = mid + 1; // 在右半部分继续查找
        }
        else {
            high = mid - 1; // 在左半部分继续查找
        }
    }
    return NULL; // 找不到，返回NULL
}