线性表的应用

一、有序表合并（归并思想）

顺序表合并：将两个有序顺序表 A、B 合并为有序顺序表 C：

bool Merge(SqList A, SqList B, SqList *C) {
    if (A.length + B.length > MaxSize) return false;
    int i = 0, j = 0, k = 0;
    while (i < A.length && j < B.length) {
        if (A.data[i] <= B.data[j]) C->data[k++] = A.data[i++];
        else                        C->data[k++] = B.data[j++];
    }
    while (i < A.length) C->data[k++] = A.data[i++];
    while (j < B.length) C->data[k++] = B.data[j++];
    C->length = k;
    return true;
}

时间复杂度 O(m+n)；空间复杂度 O(m+n)（需要新数组）。

链表合并（尾插法）：

LinkList Merge(LinkList A, LinkList B) {
    LNode *p = A->next, *q = B->next;
    LNode *r = A;  // r 指向结果链表尾部
    while (p && q) {
        if (p->data <= q->data) { r->next = p; r = p; p = p->next; }
        else                    { r->next = q; r = q; q = q->next; }
    }
    r->next = p ? p : q;  // 接上剩余部分
    free(B);
    return A;
}

时间复杂度 O(m+n)；空间复杂度 O(1)（原地合并）。

二、链表逆序（反转）

方法 1：头插法逆序——依次摘下结点，用头插法插入到头结点之后：

void Reverse(LinkList L) {
    LNode *p = L->next;
    L->next = NULL;
    while (p != NULL) {
        LNode *q = p->next;   // 保存后继
        p->next = L->next;    // 头插
        L->next = p;
        p = q;                // 继续下一个
    }
}

方法 2：三指针法（不带头结点）：

LNode* Reverse(LNode *head) {
    LNode *prev = NULL, *curr = head, *next = NULL;
    while (curr != NULL) {
        next = curr->next;    // 保存后继
        curr->next = prev;    // 反转指针
        prev = curr;  curr = next;
    }
    return prev;  // 新的头结点
}

三、查找算法

链表查找倒数第 k 个结点（双指针法）：

LNode *FindKth(LinkList L, int k) {
    LNode *fast = L->next, *slow = L->next;
    for (int i = 0; i < k; i++) {
        if (fast == NULL) return NULL;
        fast = fast->next;
    }
    while (fast != NULL) { fast = fast->next; slow = slow->next; }
    return slow;
}

查找中间结点（快慢指针）：fast 走两步，slow 走一步，fast 到末尾时 slow 在中间。

判断链表是否有环（Floyd 判圈算法）：fast 每次 2 步、slow 每次 1 步，相遇则有环。

四、链表分割

void Partition(LinkList L, ElemType x) {
    // 小于 x 的放 L1，大于等于 x 的放 L2，最后 L1->next = L2->next
    LNode *p = L->next;
    LNode *L1 = (LNode *)malloc(sizeof(LNode));  // 小于 x
    LNode *L2 = (LNode *)malloc(sizeof(LNode));  // 大于等于 x
    LNode *r1 = L1, *r2 = L2;
    while (p != NULL) {
        if (p->data < x) { r1->next = p; r1 = p; }
        else             { r2->next = p; r2 = p; }
        p = p->next;
    }
    r1->next = L2->next; r2->next = NULL;
    L->next = L1->next; free(L1); free(L2);
}

五、删除重复元素（有序链表去重）

void DeleteDuplicate(LinkList L) {
    LNode *p = L->next;
    while (p->next != NULL) {
        if (p->data == p->next->data) {
            LNode *q = p->next; p->next = q->next; free(q);
        } else { p = p->next; }
    }
}