顺序表与链表详解：结构、实现与算法分析

dynamicSequentialList.c

①初始化、销毁和打印

void DSLInit(DSL* ps) {
    ps->a = NULL;
    ps->size = ps->capacity = 0;
}

void DSLDestroy(DSL* ps) {
    free(ps->a);
    free(ps);
}

void DSLPrint(DSL* ps) {
    for (int i = 0; i < ps->size; ++i) {
        printf("%d, ", ps->a[i]);
    }
    printf("\n");
}

②扩容

void DSLCheckCapacity(DSL* ps) {
    if (ps == NULL) {
        exit(1);
    }
    if (ps->size < ps->capacity) {
        return;
    }
    int newCapacity = ps->capacity == 0 ? INIT_CAPACITY : 2 * ps->capacity;
    SLDataType* tmp = (SLDataType*)realloc(ps->a, newCapacity);
    if (tmp == NULL) {
        exit(1);
    }
    ps->a = tmp;
    ps->capacity = newCapacity;
}

1. 安全性：检查 ps 和 tmp 是否为空。
2. 是否有必要扩容：检查 size 是否小于 capacity。
3. 扩容多少空间：一般在原来基础上扩容两倍。
4. tmp 临时指针：为避免 realloc 申请不到空间，创建临时指针指向扩容后的空间。
5. 更新 a, capacity。

③头插

void DSLPushFront(DSL* ps, SLDataType x) {
    if (ps == NULL) {
        exit(1);
    }
    DSLCheckCapacity(ps);
    for (int i = ps->size; i > 0; --i) {
        ps->a[i] = ps->a[i - 1];
    }
    ps->a[0] = x;
    ++ps->size;
}

1. 安全性：检查参数 ps 是否为空，检查是否需要扩容。
2. 更新 a, size。

④头删

void DSLPopFront(DSL* ps) {
    if (ps == NULL || ps->size == 0) {
        exit(1);
    }
    for (int i = 0; i < ps->size - 1; ++i) {
        ps->a[i] = ps->a[i + 1];
    }
    ps->a[--ps->size] = 0;
}

1. 安全性：检查 ps 是否为空，检查 size 是否为 0。
2. 更新 a, size。

⑤尾插

void DSLPushBack(DSL* ps, SLDataType x) {
    if (ps == NULL) {
        exit(1);
    }
    DSLCheckCapacity(ps);
    ps->a[ps->size++] = x;
}

1. 安全性：检查参数 ps 是否为空，检查是否需要扩容。
2. 更新 a, size。

⑥尾删

void DSLPopBack(DSL* ps) {
    if (ps == NULL || ps->size == 0) {
        exit(1);
    }
    ps->a[--ps->size] = 0;
}

1. 安全性：检查 ps 是否为空，检查 size 是否为 0。
2. 更新 a, size。

⑦指定位置插入

void DSLInsert(DSL* ps, int pos, SLDataType x) {
    if (ps == NULL || pos < 0 || pos > ps->size) {
        exit(1);
    }
    DSLCheckCapacity(ps);
    for (int i = ps->size; i > pos; --i) {
        ps->a[i] = ps->a[i - 1];
    }
    ps->a[pos] = x;
    ++ps->size;
}

1. 安全性：检查参数 ps, pos 是否合法，检查是否需要扩容。
2. 更新 a, size。

⑧指定位置删除

void DSLErase(DSL* ps, int pos) {
    if (ps == NULL || ps->size == 0 || pos < 0 || pos > ps->size) {
        exit(1);
    }
    for (int i = pos; i < ps->size - 1; ++i) {
        ps->a[i] = ps->a[i + 1];
    }
    ps->a[ps->size - 1] = 0;
    --ps->size;
}

1. 安全性：检查参数 ps, pos 合法性。
2. 更新 a, size。

⑨查找元素

int DSLFind(DSL* ps, SLDataType x) {
    assert(ps);
    if (ps->size == 0) {
        perror("the list is empty");
        return -1;
    }
    for (int i = 0; i < ps->size; ++i) {
        if (ps->a[i] == x) {
            return i;
        }
    }
    return -1;
}

1. 安全性：检查参数 ps 是否为空。
2. 循环查找 x。
3. 判断循环是找到了退出，还是遍历完了没有找到退出。

（4）顺序表算法题

①移除元素

解法一

int removeElement(int* nums, int numsSize, int val) {
    int k = numsSize;
    for (int i = 0; i < k; ++i) {
        if (nums[i] == val) {
            nums[i--] = nums[--k];
        }
    }
    return k;
}

1. 遍历数组。
2. 判断是否与 val 值相等。
3. 如果与 val 值相等，则被数组最后一个元素覆盖。
4. 被覆盖后，k 值 -1。
5. 被覆盖后，还需要判断覆盖后的元素值是否与 val 值相等。

解法二：双指针法

int removeElement(int* nums, int numsSize, int val) {
    int src = 0;
    int dst = 0;
    for (int i = 0; i < numsSize; ++i) {
        if (nums[src] != val) {
            nums[dst++] = nums[src];
        }
        ++src;
    }
    return dst;
}

1. 两个指针 dst 和 src 遍历数组。
2. src 找值不等于 val 的元素。
3. 找到后把 src 指向的值赋值给 dst 指向的位置。
4. dst 向前，src 向前找下一个值不等于 val 的元素。
5. dst 的值即为最后值不等于 val 的元素的个数。

②删除有序数组中的重复项

解法一

int removeDuplicates(int* nums, int numsSize) {
    if (!numsSize) {
        return 0;
    }
    int k = 1;
    for (int i = 1; i < numsSize; ++i) {
        if (nums[i] != nums[i - 1]) {
            nums[k++] = nums[i];
        }
    }
    return k;
}

1. 数组第一个元素一定是第一个不重复的元素，k 初始化为 1。
2. 遍历数组。
3. 如果元素不等于前一个元素的值，就把这个元素放到下标为 k 的位置上，k 值加 1。
4. k 值即为最后不重复元素的个数。

解法二：双指针法

int removeDuplicates(int* nums, int numsSize) {
    int dst = 0;
    int src = 1;
    while (src < numsSize) {
        if (nums[src] != nums[dst] && ++dst != src) {
            nums[dst] = nums[src];
        }
        ++src;
    }
    return ++dst;
}

1. src 遍历数组。
2. 如果找到和 dst 指向元素的值不相等的元素，则把 src 指向的元素赋值给 dst 后一个位置。

③合并两个有序数组

解法一：先合并再冒泡排序

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {
    int i = m;
    int j = 0;
    int tmp = 0;
    int flag = 0;
    while (i < nums1Size) {
        nums1[i++] = nums2[j++];
    }
    for (i = 0; i < nums1Size; ++i) {
        flag = 0;
        for (j = 0; j < nums1Size - i - 1; ++j) {
            if (nums1[j] > nums1[j + 1]) {
                tmp = nums1[j];
                nums1[j] = nums1[j + 1];
                nums1[j + 1] = tmp;
                flag++;
            }
        }
        if (!flag) {
            break;
        }
    }
}

解法二：找最大排最后

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {
    int i = m - 1;
    int j = n - 1;
    int tail = nums1Size - 1;
    while (i >= 0 && j >= 0) {
        if (nums1[i] > nums2[j]) {
            nums1[tail--] = nums1[i--];
        } else {
            nums1[tail--] = nums2[j--];
        }
    }
    while (j >= 0) {
        nums1[tail--] = nums2[j--];
    }
}

1. i, j 分别从后往前遍历两个数组。
2. 判断下标 i 和下标 j 的值，大的放到下标 tail 的位置。
3. 更新值大的下标和 tail。
4. 如果 i 遍历结束，此时 j 还没有遍历结束，则把 nums2 剩余元素放到 nums1 中。

（5）顺序表问题与思考

1. 中间、头部插入数据，时间复杂度为 O(N)。
2. 增容（申请新空间，拷贝数据）带来的开销。
3. 增容后空间的浪费。

（三）单链表

（1）概念与结构

1. 单链表物理存储结构上非连续、非顺序。
2. 逻辑顺序通过指针链接次序实现。

链表的性质

1. 结点一般从堆上申请空间。
2. 申请空间可能不连续。

（2）实现单链表

①头插/头删

void SLLPushFront(SLLNode** pphead, SLLDataType x) {
    SLLNode* newNode = SLLBuyNode(x);
    if (*pphead == NULL) {
        *pphead = newNode;
        return;
    }
    newNode->next = *pphead;
    *pphead = newNode;
}

1. 申请新节点。
2. 链表为空特殊处理，return。

void SLLPopFront(SLLNode** pphead) {
    assert(pphead && *pphead);
    SLLNode* phead = *pphead;
    *pphead = phead->next;
    free(phead);
}

1. 确保链表不为 NULL。
2. 释放原来表头节点空间。
3. 表头节点更新。

②尾插/尾删

void SLLPushBack(SLLNode** pphead, SLLDataType x) {
    SLLNode* newNode = SLLBuyNode(x);
    if (*pphead == NULL) {
        *pphead = newNode;
        return;
    }
    SLLNode* cur = *pphead;
    while (cur->next != NULL) {
        cur = cur->next;
    }
    cur->next = newNode;
}

1. 申请新节点。
2. 链表为空特殊处理，return。
3. 遍历到表尾节点，在其后插入新节点。

void SLLPopBack(SLLNode** pphead) {
    assert(pphead && *pphead);
    SLLNode* tail = *pphead;
    SLLNode* prev = tail;
    if (tail->next == NULL) {
        free(tail);
        *pphead = NULL;
        return;
    }
    while (tail->next != NULL) {
        prev = tail;
        tail = tail->next;
    }
    prev->next = NULL;
    free(tail);
}

1. 确保链表不为 NULL。
2. 链表只有一个节点特殊处理，return。
3. 遍历到表尾节点，更新 prev->next 指针。
4. 释放原表尾节点空间。

③查找

SLLNode* SLLFind(SLLNode* phead, SLLDataType x) {
    assert(phead);
    SLLNode* cur = phead;
    while (cur != NULL && cur->data != x) {
        cur = cur->next;
    }
    if (cur == NULL) {
        printf("not query data found!\n");
    }
    return cur;
}

1. 确保链表不为 NULL。
2. 遍历链表，直到找到指定节点的值=给定值。
3. 如果遍历完链表，都没找到，则返回 NULL。

④在指定位置之前插入数据

void SLLInsert(SLLNode** pphead, SLLNode* pos, SLLDataType x) {
    assert(pphead && pos && x);
    SLLNode* newNode = SLLBuyNode(x);
    if (*pphead == pos) {
        newNode->next = *pphead;
        *pphead = newNode;
        return;
    }
    SLLNode* cur = *pphead;
    while (cur != NULL && cur->next != pos) {
        cur = cur->next;
    }
    if (cur == NULL) {
        perror("invalid input");
        exit(1);
    }
    newNode->next = pos;
    cur->next = newNode;
}

1. 确保链表和指定位置地址不为 NULL。
2. 创建指定值的新节点。
3. 指定位置为表头节点特殊处理，return。
4. 遍历链表，直到指定位置之前的节点。
5. 修改该节点和新节点的 next。
6. 如果遍历完链表，都未找到指定位置，则报错后 exit。

⑤删除指定节点

void SLLErase(SLLNode** pphead, SLLNode* pos) {
    if (pphead == NULL || *pphead == NULL || pos == NULL) {
        perror("invalid input");
        exit(1);
    }
    if (*pphead == pos) {
        *pphead = pos->next;
        free(pos);
        return;
    }
    SLLNode* cur = *pphead;
    assert(cur);
    while (cur->next != pos) {
        cur = cur->next;
    }
    cur->next = pos->next;
    free(pos);
}

1. 确保链表和指定位置不为 NULL。
2. 指定位置为表头结点特殊处理，return。
3. 遍历链表，直到指定位置之前节点。
4. 更改该节点的 next。
5. 释放指定位置空间。

⑥在指定位置之后插入数据

void SLLInsertAfter(SLLNode* pos, SLLDataType x) {
    assert(pos);
    SLLNode* newNode = SLLBuyNode(x);
    newNode->next = pos->next;
    pos->next = newNode;
}

1. 确保指定位置不为 NULL。
2. 创建新节点。
3. 更改新节点和指定位置节点的 next。

⑦删除在指定位置之后的节点

void SLLEraseAfter(SLLNode* pos) {
    assert(pos);
    SLLNode* cur = pos->next;
    if (cur == NULL) {
        return;
    }
    SLLNode* next = NULL;
    pos->next = NULL;
    while (cur != NULL) {
        next = cur->next;
        free(cur);
        cur = next;
    }
}

1. 确保指定位置不为 NULL。
2. 指定位置节点的 next 为 NULL 特殊处理，return。
3. 遍历链表，直到指定位置之后。
4. next 保存 cur->next 的数据。
5. 依次释放 cur 的空间，直到 cur 为 NULL。

⑧销毁链表

void SLLDestory(SLLNode** pphead) {
    if (*pphead == NULL) {
        perror("invalid input!");
        exit(1);
    }
    SLLNode* cur = *pphead;
    *pphead = NULL;
    SLLNode* next = NULL;
    while (cur != NULL) {
        next = cur->next;
        free(cur);
        cur = next;
    }
}

1. 链表为 NULL 特殊处理，exit。
2. cur 遍历链表。
3. next 保存 cur->next 的数据。
4. 依次释放 cur 的空间，直到 cur 为 NULL。

（3）链表的分类

①单向和双向

实际中最常用结构：单链表和双向带头循环链表。

②带头和不带头

③循环和不循环

（4）单链表算法题

①移除链表元素

struct ListNode* removeElements(struct ListNode* head, int val) {
    struct ListNode* cur = head;
    struct ListNode* prev = head;
    while (cur != NULL) {
        if (head->val == val) {
            head = prev = cur = cur->next;
            continue;
        }
        if (cur->val == val) {
            prev->next = cur->next;
            free(cur);
        } else {
            prev = cur;
        }
        cur = prev->next;
    }
    return head;
}

1. cur 循环遍历链表。
2. 如果 head 的值与指定值相等，则特殊处理，continue。
3. 如果 cur 节点需要删除，则删除后，更新 cur。
4. 如果 cur 节点不需要删除，则更新 prev 和 cur 节点。

②反转链表

struct ListNode* reverseList(struct ListNode* head) {
    if (head == NULL || head->next == NULL) {
        return head;
    }
    struct ListNode* cur = head->next;
    struct ListNode* prev = head;
    struct ListNode* next;
    while (cur != NULL) {
        next = cur->next;
        if (prev == head) {
            prev->next = NULL;
        }
        cur->next = prev;
        prev = cur;
        cur = next;
    }
    return prev;
}

1. 链表为空或只有一个节点，特殊处理，返回链表。
2. prev 为 head 时特殊处理，prev->next 置为 NULL。
3. cur 遍历链表，prev, next 和 next 依次更新。
4. 最后 cur 为 NULL，返回 prev。

③合并两个有序链表

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    if (list1 == NULL) {
        return list2;
    }
    if (list2 == NULL) {
        return list1;
    }
    if (list1->val > list2->val) {
        struct ListNode* tmp = list1;
        list1 = list2;
        list2 = tmp;
    }
    struct ListNode* plt1 = list1->next;
    struct ListNode* plt2 = list2;
    struct ListNode* next;
    struct ListNode* prev = list1;
    while (plt1 && plt2) {
        if (plt1->val <= plt2->val) {
            prev = plt1;
            plt1 = plt1->next;
        } else {
            next = plt2->next;
            plt2->next = plt1;
            prev->next = plt2;
            prev = plt2;
            plt2 = next;
        }
    }
    while (plt2) {
        prev->next = plt2;
        prev = prev->next;
        plt2 = plt2->next;
    }
    return list1;
}

1. list1 或 list2 为 NULL 时，特殊处理，return 原链表。
2. 确保表头结点小的那个链表是 list1。
3. plt1 遍历 list1, plt2 遍历 list2。
4. prev 为 plt1 前一个节点，next 是 plt2 的下一个节点，方便 plt2 更新。
5. 进入循环，若 plt2 的值小，则插入 list1。
6. 最后若 list2 还有剩余的节点，则直接接到 list1 尾部。

④链表的回文结构

封装函数 reverseList

ListNode* reverseList(ListNode* head) {
    if (head == NULL || head->next == NULL) {
        return head;
    }
    ListNode* cur = head->next;
    ListNode* prev = head;
    ListNode* next;
    while (cur != NULL) {
        next = cur->next;
        if (prev == head) {
            prev->next = NULL;
        }
        cur->next = prev;
        prev = cur;
        cur = next;
    }
    return prev;
}

题目所求函数

bool chkPalindrome(ListNode* A) {
    if (A == NULL || A->next == NULL) {
        return false;
    }
    ListNode* slow = A;
    ListNode* fast = A;
    while (fast) {
        slow = slow->next;
        fast = fast->next;
        if (fast) {
            fast = fast->next;
        }
    }
    ListNode* curA = A;
    ListNode* curB = reverseList(slow);
    while (curA && curB) {
        if (curA->val != curB->val) {
            return false;
        }
        curA = curA->next;
        curB = curB->next;
    }
    return true;
}

1. 特殊情况：链表为空，链表只有一个节点。
2. 快慢指针找到链表后半部分，slow 即为后半部分的表头节点。
3. 反转链表后半部分。
4. 比较 链表前半部分 和 反转后链表后半部分，若各值对应相等，顺利退出循环，则为回文字符结构。
5. 若循环中断，则不为回文字符结构。

⑤相交链表

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    if (headA == headB) {
        return headA;
    }
    struct ListNode* cur1 = headA;
    int size1 = 0;
    while (cur1) {
        ++size1;
        cur1 = cur1->next;
    }
    struct ListNode* cur2 = headB;
    int size2 = 0;
    while (cur2) {
        ++size2;
        cur2 = cur2->next;
    }
    int gap = 0;
    cur1 = headA;
    cur2 = headB;
    if (size1 > size2) {
        gap = size1 - size2;
        while (gap) {
            cur1 = cur1->next;
            gap--;
        }
    } else {
        gap = size2 - size1;
        while (gap) {
            cur2 = cur2->next;
            gap--;
        }
    }
    while (cur1 && cur2 && cur1 != cur2) {
        cur1 = cur1->next;
        cur2 = cur2->next;
    }
    if (!cur1 || !cur2) {
        return NULL;
    }
    return cur1;
}

1. 处理特殊情况：两链表完全相同，有一链表为 NULL。
2. cur1, cur2 循环遍历链表，累加求得两链表 size 的值。
3. size 相减求得 gap。
4. cur1 或 cur2 需要先走 gap 步。
5. 后两指针同时遍历两链表。
6. 若有相同的节点，即为相交节点。
7. 若遍历结束都没有相同的节点，则返回 NULL。

⑥环形链表Ⅰ

快慢指针解法

bool hasCycle(struct ListNode *head) {
    if (head == NULL || head->next == NULL) {
        return false;
    }
    struct ListNode* slow = head->next;
    struct ListNode* fast = slow->next;
    while (fast && slow != fast) {
        slow = slow->next;
        if (fast->next != NULL) {
            fast = fast->next->next;
        } else {
            fast = NULL;
        }
    }
    if (slow == fast) {
        return true;
    } else {
        return false;
    }
}

1. 特殊情况 return false：如果链表为空，或链表只有一个节点且 next 为 NULL。
2. 慢指针一次走一步，快指针一次走两步。
3. 若链表带环，则快慢指针会相遇，return true。
4. 若链表不带环，则快指针先走到 NULL，return false。

（四）双向链表

（1）概念与结构

带头双向链表：这里的头节点不保存有效数据，可以看作'哨兵位'。

（2）实现双向链表

①初始化等操作

函数 DLLInit

DLLNode* DLLInit() {
    DLLNode* phead = BuyNode(-1);
    phead->prev = phead;
    phead->next = phead;
    return phead;
}

1. 为头节点开辟空间。
2. 初始化头节点的 prev 和 next。
3. 返回头节点。

函数 DLLDestory

void DLLDestory(DLLNode* phead) {
    if (phead == NULL) {
        perror("the phead is NULL");
        exit(1);
    }
    if (phead->next != phead) {
        DLLNode* cur = phead->next;
        DLLNode* next = NULL;
        while (cur != phead) {
            next = cur->next;
            free(cur);
            cur = next;
        }
    }
    free(phead);
    phead = NULL;
}

1. 特殊情况：头节点为 NULL，链表只有一个节点。
2. cur 遍历链表，next 保存下一个节点，依次销毁。

函数 DLLEmpty

bool DLLEmpty(DLLNode* phead) {
    if (phead == NULL) {
        perror("the phead is NULL");
        exit(1);
    }
    if (phead->next == phead) {
        return true;
    }
    return false;
}

1. 特殊情况：头节点为 NULL。
2. 若头节点的 next 仍为头节点，即链表为 empty。

函数 DLLPrint

void DLLPrint(DLLNode* phead) {
    if (DLLEmpty(phead)) {
        printf("NULL\n");
    }
    DLLNode* cur = phead->next;
    while (cur != phead) {
        printf("%d->", cur->data);
        cur = cur->next;
    }
    printf("\n");
}

1. 特殊情况：链表为 empty。
2. cur 遍历链表，依次打印。

②头插/头删

函数 DLLPushFront

void DLLPushFront(DLLNode* phead, DLLDataType x) {
    if (phead == NULL) {
        perror("the phead is NULL");
        exit(1);
    }
    DLLNode* newNode = BuyNode(x);
    newNode->next = phead->next;
    newNode->prev = phead;
    phead->next->prev = newNode;
    phead->next = newNode;
}

1. 特殊情况：头节点为 NULL。
2. 创建新节点。
3. 处理 newNode, phead 和 next 的链接关系。

函数 DLLPopFront

void DLLPopFront(DLLNode* phead) {
    if (DLLEmpty(phead)) {
        printf("operation invalid\n");
        return;
    }
    DLLNode* front = phead->next;
    front->next->prev = phead;
    phead->next = front->next;
    free(front);
}

1. 特殊情况：链表为 empty。
2. 处理 phead 和 next 的链接关系。
3. 释放 front 的节点空间。

③尾插/尾删

函数 DLLPushBack

void DLLPushBack(DLLNode* phead, DLLDataType x) {
    DLLNode* newNode = BuyNode(x);
    if (DLLEmpty(phead)) {
        newNode->prev = phead;
        phead->next = newNode;
    } else {
        newNode->prev = phead->prev;
        phead->prev->next = newNode;
    }
    newNode->next = phead;
    phead->prev = newNode;
}

1. 创建新节点。
2. 特殊情况：链表为 empty，处理头结点的 prev 和 next。
3. 一般情况：链表不为 empty，处理 表尾节点、newNode 和 phead 的链接关系。

函数 DLLPopBack

void DLLPopBack(DLLNode* phead) {
    if (DLLEmpty(phead)) {
        printf("operation invalid\n");
        return;
    }
    DLLNode* ptail = phead->prev;
    DLLNode* prev = ptail->prev;
    prev->next = phead;
    phead->prev = prev;
    free(ptail);
    ptail = NULL;
}

1. 特殊情况：链表为 empty。
2. 定义 ptail 表尾节点，处理 prev 和 phead 的链接关系。
3. 释放 ptail 空间。

④指定位置

函数 DLLInsert

void DLLInsert(DLLNode* pos, DLLDataType x) {
    if (pos == NULL || pos->prev == NULL || pos->next == NULL) {
        printf("operation invalid\n");
        return;
    }
    DLLNode* newNode = BuyNode(x);
    newNode->next = pos->next;
    newNode->prev = pos;
    pos->next->prev = newNode;
    pos->next = newNode;
}

1. 特殊情况：pos 为 NULL，pos 的 prev 和 next 为 NULL。
2. 创建新节点。
3. 处理 pos, newNode 和 pos->next 的链接关系。

函数 DLLErase

void DLLErase(DLLNode* pos) {
    if (pos == NULL || pos->prev == NULL || pos->next == NULL) {
        printf("operation invalid\n");
        return;
    }
    pos->next->prev = pos->prev;
    pos->prev->next = pos->next;
    free(pos);
    pos = NULL;
}

1. 特殊情况：pos 为 NULL，pos 的 prev 和 next 为 NULL。
2. 处理 pos->prev 和 pos->next 的链接关系。
3. 释放 pos 的节点空间。

⑤查找节点

函数 DLLFind

DLLNode* DLLFind(DLLNode* phead, DLLDataType x) {
    if (DLLEmpty(phead)) {
        printf("operation invalid\n");
        return NULL;
    }
    DLLNode* cur = phead->next;
    while (cur != phead) {
        if (cur->data == x) {
            return cur;
        }
        cur = cur->next;
    }
    return NULL;
}

1. 特殊情况：链表为 empty。
2. cur 遍历链表，若找到了，则返回节点地址。
3. 若遍历结束，还未找到，则返回 NULL。

（五）顺序表与链表的分析