线性表：顺序表与单链表、双向链表的完整实现与对比分析

#define MAX_SIZE 100
 
// 静态顺序表：定长数组 + 有效个数
typedef struct SeqList
{
    int a[MAX_SIZE];   // 定长数组，容量写死
    int size;          // 有效数据个数
} SeqList;

// SeqList.h
#pragma once
#include <stdio.h>
#include <stdlib.h>
 
#define INIT_CAPACITY 4
 
typedef int SLDataType;   // 数据类型的"统一出口"，想存别的类型改这一处
 
// 动态顺序表 -- 按需申请
typedef struct SeqList
{
    SLDataType* a;        // 指向动态申请的数组空间
    int size;             // 有效数据个数
    int capacity;         // 空间容量
} SL;
 
// 初始化和销毁
void SLInit(SL* ps);
void SLDestroy(SL* ps);
void SLPrint(SL* ps);
 
// 扩容
void SLCheckCapacity(SL* ps);
 
// 头部插入删除 / 尾部插入删除
void SLPushBack(SL* ps, SLDataType x);
void SLPopBack(SL* ps);
void SLPushFront(SL* ps, SLDataType x);
void SLPopFront(SL* ps);
 
// 指定位置之前插入 / 删除数据
void SLInsert(SL* ps, int pos, SLDataType x);
void SLErase(SL* ps, int pos);
 
// 查找
int SLFind(SL* ps, SLDataType x);

// SeqList.c
#include "SeqList.h"
 
// 初始化：一个元素都没有，空间也还没申请
void SLInit(SL* ps)
{
    ps->a = NULL;
    ps->size = 0;
    ps->capacity = 0;
}
 
// 销毁：释放动态内存，防止内存泄漏
void SLDestroy(SL* ps)
{
    free(ps->a);          // 释放动态申请的数组
    ps->a = NULL;         // 置空，防止野指针
    ps->size = 0;
    ps->capacity = 0;
}
 
// 打印：遍历输出所有有效数据
void SLPrint(SL* ps)
{
    for (int i = 0; i < ps->size; i++)
    {
        printf("%d ", ps->a[i]);
    }
    printf("\n");
}

// 检查容量：满了就扩容，采用 2 倍策略
void SLCheckCapacity(SL* ps)
{
    if (ps->size == ps->capacity)   // 满了才扩容
    {
        // 新容量：旧容量为 0（刚初始化）时先给 INIT_CAPACITY，否则翻倍
        int newCapacity = (ps->capacity == 0) ? INIT_CAPACITY : ps->capacity * 2;
        SLDataType* tmp = (SLDataType*)realloc(ps->a, newCapacity * sizeof(SLDataType));
        if (tmp == NULL)            // realloc 失败返回 NULL，不能直接覆盖 ps->a
        {
            perror("realloc fail");
            exit(1);
        }
        ps->a = tmp;                // 扩容成功，更新指针
        ps->capacity = newCapacity; // 更新容量
    }
}

// 尾插：新数据放在最后面
void SLPushBack(SL* ps, SLDataType x)
{
    SLCheckCapacity(ps);            // 先确保有空间
    ps->a[ps->size] = x;            // 新数据放在最后一个有效位置之后
    ps->size++;
}
 
// 尾删：直接把有效个数减一即可
void SLPopBack(SL* ps)
{
    if (ps->size == 0)              // 边界：空表不能删
        return;
    ps->size--;                     // 逻辑上"看不见"最后一个元素了
}

// 头插：所有数据后移一位，再把新数据放到最前面
void SLPushFront(SL* ps, SLDataType x)
{
    SLCheckCapacity(ps);
    int end = ps->size - 1;         // 从最后一个元素开始往后搬
    while (end >= 0)
    {
        ps->a[end + 1] = ps->a[end];// 每个元素搬到它的后一个位置
        end--;
    }
    ps->a[0] = x;                   // 腾出位置 0，放入新数据
    ps->size++;
}
 
// 头删：所有数据前移一位，覆盖掉第一个元素
void SLPopFront(SL* ps)
{
    if (ps->size == 0)
        return;
    int begin = 0;
    while (begin < ps->size - 1)
    {
        ps->a[begin] = ps->a[begin + 1]; // 每个元素往前挪一位
        begin++;
    }
    ps->size--;
}

// 在 pos 位置之前插入数据（pos 是下标）
void SLInsert(SL* ps, int pos, SLDataType x)
{
    if (pos < 0 || pos > ps->size)  // 合法范围：[0, size]，pos == size 等价于尾插
        return;
    SLCheckCapacity(ps);
    int end = ps->size - 1;
    while (end >= pos)              // 从后往前搬，避免覆盖
    {
        ps->a[end + 1] = ps->a[end];
        end--;
    }
    ps->a[pos] = x;                 // 空出来的位置放新数据
    ps->size++;
}
 
// 删除 pos 位置的数据
void SLErase(SL* ps, int pos)
{
    if (pos < 0 || pos >= ps->size) // 越界直接返回
        return;
    int begin = pos;
    while (begin < ps->size - 1)    // 从前往后搬，覆盖掉 pos 位置
    {
        ps->a[begin] = ps->a[begin + 1];
        begin++;
    }
    ps->size--;
}
 
// 查找：找到返回下标，找不到返回 -1
int SLFind(SL* ps, SLDataType x)
{
    for (int i = 0; i < ps->size; i++)
    {
        if (ps->a[i] == x)
            return i;
    }
    return -1;
}

// Test.c
#include "SeqList.h"
 
int main()
{
    SL s;
    SLInit(&s);
 
    SLPushBack(&s, 1);
    SLPushBack(&s, 2);
    SLPushBack(&s, 3);
    SLPushBack(&s, 4);
    SLPrint(&s);                 // 1 2 3 4
 
    SLPushBack(&s, 5);           // 容量 4 满了，触发扩容
    SLPrint(&s);                 // 1 2 3 4 5
 
    SLPopBack(&s);
    SLPrint(&s);                 // 1 2 3 4
 
    SLPushFront(&s, 0);
    SLPrint(&s);                 // 0 1 2 3 4
 
    SLPopFront(&s);
    SLPrint(&s);                 // 1 2 3 4
 
    SLInsert(&s, 2, 99);         // 在下标 2 之前插入 99
    SLPrint(&s);                 // 1 2 99 3 4
 
    SLErase(&s, 2);              // 删除下标 2 的元素
    SLPrint(&s);                 // 1 2 3 4
 
    int pos = SLFind(&s, 3);
    printf("3 的位置是 %d\n", pos); // 2
 
    SLDestroy(&s);               // 用完释放，养成好习惯
    return 0;
}

总拷贝量 = 4 + 8 + 16 + ... + 2^k      （k ≈ log₂N）
         ≈ 2^(k+1) - 4
         ≈ 2N - 4                        ← 等比数列求和，最大的那一项已经接近 2N

// LeetCode 27. 移除元素：原地移除所有值等于 val 的元素
// 思路：双指针，src 遍历，dst 记录保留元素该放的位置
int removeElement(int* nums, int numsSize, int val)
{
    int src = 0;   // 快指针：遍历原数组
    int dst = 0;   // 慢指针：保留元素的位置
    while (src < numsSize)
    {
        if (nums[src] != val)      // 找到要保留的元素
        {
            nums[dst] = nums[src]; // 往前搬
            dst++;
        }
        src++;
    }
    return dst;    // dst 就是新数组的长度
}

// LeetCode 26. 删除有序数组中的重复项
// 思路：有序 => 重复元素相邻，双指针原地去重
int removeDuplicates(int* nums, int numsSize)
{
    if (numsSize == 0)             // 空数组直接返回
        return 0;
    int dst = 0;                   // 已去重区域的最后一个下标
    for (int src = 1; src < numsSize; src++)
    {
        if (nums[src] != nums[dst])// 遇到新元素
        {
            dst++;
            nums[dst] = nums[src]; // 放到去重区域末尾
        }
    }
    return dst + 1;                // 长度 = 最后一个保留元素下标 + 1
}

// LeetCode 88. 合并两个有序数组
// 思路：从后往前归并，避免覆盖 nums1 中尚未处理的有效数据
void merge(int* nums1, int nums1Size, int m,
           int* nums2, int nums2Size, int n)
{
    int end1 = m - 1;          // nums1 有效数据的最后一个位置
    int end2 = n - 1;          // nums2 的最后一个位置
    int end = m + n - 1;       // 合并后数组的最后一个位置
 
    while (end1 >= 0 && end2 >= 0)   // 两边都还有数据时
    {
        if (nums1[end1] > nums2[end2])   // 谁大谁放后面
            nums1[end--] = nums1[end1--];
        else
            nums1[end--] = nums2[end2--];
    }
    // 如果 nums2 还有剩余，全部搬到前面
    // （nums1 还有剩余时不用管，它本来就在正确的位置）
    while (end2 >= 0)
    {
        nums1[end--] = nums2[end2--];
    }
}

// 单链表结点：数据 + 指向下一个结点的指针
struct SListNode
{
    int data;                 // 结点数据
    struct SListNode* next;   // 保存下一个结点的地址
};

// SList.h
#pragma once
#include <stdio.h>
#include <stdlib.h>
 
typedef int SLTDataType;
 
typedef struct SListNode
{
    SLTDataType data;          // 结点数据
    struct SListNode* next;    // 保存下一个结点的地址
} SLTNode;
 
void SLTPrint(SLTNode* phead);
 
// 头部插入删除 / 尾部插入删除（注意：全部传二级指针！）
void SLTPushBack(SLTNode** pphead, SLTDataType x);
void SLTPushFront(SLTNode** pphead, SLTDataType x);
void SLTPopBack(SLTNode** pphead);
void SLTPopFront(SLTNode** pphead);
 
// 查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);
 
// 在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
// 删除 pos 结点
void SLTErase(SLTNode** pphead, SLTNode* pos);
// 在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x);
// 删除 pos 之后的结点
void SLTEraseAfter(SLTNode* pos);
 
// 销毁链表
void SListDestroy(SLTNode** pphead);

// SList.c
#include "SList.h"
 
// 打印：从头结点开始，沿着 next 一路走到底
void SLTPrint(SLTNode* phead)
{
    SLTNode* cur = phead;
    while (cur != NULL)
    {
        printf("%d -> ", cur->data);
        cur = cur->next;          // 走到下一个结点
    }
    printf("NULL\n");
}
 
// 申请一个新结点：每次插入之前都要先申请
SLTNode* BuySLTNode(SLTDataType x)
{
    SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
    if (newnode == NULL)
    {
        perror("malloc fail");
        exit(1);
    }
    newnode->data = x;
    newnode->next = NULL;
    return newnode;
}

// 尾插：新结点挂在链表末尾
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
    SLTNode* newnode = BuySLTNode(x);
 
    // 情况一：链表为空，新结点直接成为头结点（必须改头指针！）
    if (*pphead == NULL)
    {
        *pphead = newnode;
        return;
    }
 
    // 情况二：链表非空，找到最后一个结点，让它的 next 指向新结点
    SLTNode* tail = *pphead;
    while (tail->next != NULL)    // tail 走到最后一个结点
    {
        tail = tail->next;
    }
    tail->next = newnode;         // 挂上去
}
 
// 头插：新结点永远插在最前面，头指针指向新结点
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
    SLTNode* newnode = BuySLTNode(x);
    newnode->next = *pphead;      // 新结点指向原来的头结点
    *pphead = newnode;            // 头指针指向新结点
}

// 尾删：删除最后一个结点
void SLTPopBack(SLTNode** pphead)
{
    // 边界一：空链表，什么都不做
    if (*pphead == NULL)
        return;
 
    // 边界二：只有一个结点，删除后头指针要置空
    if ((*pphead)->next == NULL)
    {
        free(*pphead);
        *pphead = NULL;
        return;
    }
 
    // 一般情况：找到倒数第二个结点
    SLTNode* prev = NULL;         // 记录 tail 的前一个
    SLTNode* tail = *pphead;
    while (tail->next != NULL)
    {
        prev = tail;
        tail = tail->next;
    }
    free(tail);                   // 释放最后一个结点
    prev->next = NULL;            // 倒数第二个的 next 置空，链表闭合
}
 
// 头删：删除第一个结点
void SLTPopFront(SLTNode** pphead)
{
    if (*pphead == NULL)          // 空链表
        return;
    SLTNode* next = (*pphead)->next;  // 先保存第二个结点
    free(*pphead);                    // 释放头结点
    *pphead = next;                   // 头指针指向第二个结点
}

// 查找：返回第一个匹配的结点地址，找不到返回 NULL
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
    SLTNode* cur = phead;
    while (cur != NULL)
    {
        if (cur->data == x)
            return cur;
        cur = cur->next;
    }
    return NULL;
}
 
// 在 pos 之前插入（pos 由 SLTFind 查找得到）
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
    if (pos == *pphead)           // pos 是头结点：等价于头插
    {
        SLTPushFront(pphead, x);
        return;
    }
    SLTNode* prev = *pphead;
    while (prev->next != pos)     // 找到 pos 的前一个结点
    {
        prev = prev->next;
    }
    SLTNode* newnode = BuySLTNode(x);
    prev->next = newnode;         // 先让前一个结点指向新结点
    newnode->next = pos;          // 再让新结点指向 pos
}
 
// 删除 pos 结点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
    if (pos == *pphead)           // 删头结点：等价于头删
    {
        SLTPopFront(pphead);
        return;
    }
    SLTNode* prev = *pphead;
    while (prev->next != pos)     // 找到 pos 的前一个结点
    {
        prev = prev->next;
    }
    prev->next = pos->next;       // 前一个结点越过 pos 指向它的后继
    free(pos);                    // 释放 pos
}
 
// 在 pos 之后插入：不需要改头指针，一级指针就够
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
    SLTNode* newnode = BuySLTNode(x);
    newnode->next = pos->next;    // 先连后面的结点（顺序不能反！）
    pos->next = newnode;          // 再让 pos 指向新结点
}
 
// 删除 pos 之后的结点
void SLTEraseAfter(SLTNode* pos)
{
    if (pos == NULL || pos->next == NULL)  // 没有后继可删
        return;
    SLTNode* del = pos->next;     // 要删的结点
    pos->next = del->next;        // pos 越过 del，直接指向 del 的后继
    free(del);                    // 释放 del
}
 
// 销毁链表：逐个释放所有结点，防内存泄漏
void SListDestroy(SLTNode** pphead)
{
    SLTNode* cur = *pphead;
    while (cur != NULL)
    {
        SLTNode* next = cur->next;  // 先保存下一个，再释放当前
        free(cur);
        cur = next;
    }
    *pphead = NULL;                 // 头指针置空
}

// LeetCode 203. 移除链表元素
// 思路：prev 记录前驱，删非头结点时修改 prev->next
struct ListNode* removeElements(struct ListNode* head, int val)
{
    // 先处理头部连续等于 val 的结点
    while (head != NULL && head->val == val)
    {
        struct ListNode* del = head;
        head = head->next;
        free(del);
    }
    // 再处理中间和尾部
    struct ListNode* prev = head;
    struct ListNode* cur = head == NULL ? NULL : head->next;
    while (cur != NULL)
    {
        if (cur->val == val)
        {
            prev->next = cur->next;   // 前驱越过 cur
            free(cur);
            cur = prev->next;         // cur 后移
        }
        else
        {
            prev = cur;
            cur = cur->next;
        }
    }
    return head;
}

// LeetCode 83. 删除排序链表中的重复元素
// 思路：有序 => 重复相邻；cur 不动反复删，直到当前值和下一个不同
struct ListNode* deleteDuplicates(struct ListNode* head)
{
    struct ListNode* cur = head;
 
    while (cur != NULL && cur->next != NULL)
    {
        if (cur->val == cur->next->val)
        {
            struct ListNode* del = cur->next;  // 记下要删的结点
            cur->next = del->next;             // cur 越过 del
            free(del);                         // 释放 del
        }
        else
        {
            cur = cur->next;   // 值不同，cur 才往前走
        }
    }
    return head;
}

// LeetCode 206. 反转链表（三指针法）
struct ListNode* reverseList(struct ListNode* head)
{
    struct ListNode* n1 = NULL;   // 新链表头，初始为空
    struct ListNode* n2 = head;   // 当前要处理的结点
    struct ListNode* n3 = NULL;   // 保存 n2 的下一个，防止断链
 
    while (n2 != NULL)
    {
        n3 = n2->next;   // ① 先保存后继
        n2->next = n1;   // ② 掉头：当前结点指向前驱
        n1 = n2;         // ③ 三个指针整体后移
        n2 = n3;
    }
    return n1;           // 原链表最后一个结点，现在是新链表头
}

// LeetCode 876. 链表的中间结点
// 思路：快慢指针，fast 到终点时 slow 刚好在中间
struct ListNode* middleNode(struct ListNode* head)
{
    struct ListNode* slow = head;
    struct ListNode* fast = head;
    while (fast != NULL && fast->next != NULL)
    {
        slow = slow->next;          // 慢指针一步
        fast = fast->next->next;    // 快指针两步
    }
    return slow;
}

// 链表中倒数第 k 个结点
// 思路：fast 先走 k 步，再和 slow 同步走，fast 到 NULL 时 slow 就是倒数第 k 个
struct ListNode* getKthFromEnd(struct ListNode* head, int k)
{
    struct ListNode* fast = head;
    struct ListNode* slow = head;
 
    while (k--)            // ① fast 先走 k 步
    {
        if (fast == NULL)  // 链表长度不足 k，倒数第 k 个不存在
            return NULL;
        fast = fast->next;
    }
 
    while (fast != NULL)   // ② 两个指针同步走，fast 到 NULL 停止
    {
        fast = fast->next;
        slow = slow->next;
    }
    return slow;           // ③ slow 就是倒数第 k 个结点
}

// LeetCode 21. 合并两个有序链表
// 思路：双指针归并 + 哨兵位头结点简化头指针处理
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{
    struct ListNode* phead = (struct ListNode*)malloc(sizeof(struct ListNode)); // 哨兵位
    struct ListNode* tail = phead;   // tail 指向新链表尾部
 
    while (list1 != NULL && list2 != NULL)
    {
        if (list1->val < list2->val) // 谁小接谁
        {
            tail->next = list1;
            list1 = list1->next;
        }
        else
        {
            tail->next = list2;
            list2 = list2->next;
        }
        tail = tail->next;
    }
    // 剩余部分直接接上（最多只剩一条链）
    tail->next = (list1 != NULL) ? list1 : list2;
 
    struct ListNode* head = phead->next; // 真正的头是哨兵位的后继
    free(phead);                         // 释放哨兵位
    return head;
}

// 链表分割：小于 x 的在前，大于等于 x 的在后
struct ListNode* partition(struct ListNode* pHead, int x)
{
    // 两个哨兵位，分别挂两段结点
    struct ListNode* lessHead = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* greaterHead = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* lessTail = lessHead;
    struct ListNode* greaterTail = greaterHead;
 
    struct ListNode* cur = pHead;
    while (cur != NULL)
    {
        if (cur->val < x)            // 小于 x 挂到 less 段
        {
            lessTail->next = cur;
            lessTail = cur;
        }
        else                         // 其余挂到 greater 段
        {
            greaterTail->next = cur;
            greaterTail = cur;
        }
        cur = cur->next;
    }
    greaterTail->next = NULL;        // 尾结点要收口，否则可能带环！
    lessTail->next = greaterHead->next;  // 两段拼接
 
    struct ListNode* head = lessHead->next;
    free(lessHead);
    free(greaterHead);
    return head;
}

// 回文结构：找中间 + 反转后半 + 双指针比对
bool chkPalindrome(struct ListNode* A)
{
    // ① 快慢指针找中间结点
    struct ListNode* slow = A;
    struct ListNode* fast = A;
    while (fast != NULL && fast->next != NULL)
    {
        slow = slow->next;
        fast = fast->next->next;
    }
    // ② 反转 slow 之后的后半段
    struct ListNode* n1 = NULL;
    struct ListNode* n2 = slow;
    struct ListNode* n3 = NULL;
    while (n2 != NULL)
    {
        n3 = n2->next;
        n2->next = n1;
        n1 = n2;
        n2 = n3;
    }
    // ③ 头指针和反转后的头（n1）同步走，比对值
    struct ListNode* head = A;
    while (n1 != NULL)
    {
        if (head->val != n1->val)
            return false;
        head = head->next;
        n1 = n1->next;
    }
    return true;
}

// LeetCode 160. 相交链表
// 思路：先对齐（长链表先走长度差），再同步走找交点
struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB)
{
    struct ListNode* curA = headA;
    struct ListNode* curB = headB;
    int lenA = 0, lenB = 0;
 
    // ① 数长度（顺便可以判断尾结点是否相同，不同则必不相交）
    while (curA != NULL) { lenA++; curA = curA->next; }
    while (curB != NULL) { lenB++; curB = curB->next; }
 
    // ② 长链表先走差值步
    int gap = abs(lenA - lenB);
    struct ListNode* longList = lenA > lenB ? headA : headB;
    struct ListNode* shortList = lenA > lenB ? headB : headA;
    while (gap--)
    {
        longList = longList->next;
    }
 
    // ③ 同步走，找第一个相同的结点
    while (longList != shortList)
    {
        longList = longList->next;
        shortList = shortList->next;
    }
    return longList;   // 可能同时为 NULL（不相交），也符合语义
}

// LeetCode 141. 环形链表 I：判断链表是否有环
bool hasCycle(struct ListNode* head)
{
    struct ListNode* slow = head;
    struct ListNode* fast = head;
    while (fast != NULL && fast->next != NULL)   // 无环时 fast 先到头
    {
        slow = slow->next;           // 慢指针一次一步
        fast = fast->next->next;     // 快指针一次两步
        if (slow == fast)            // 相遇说明有环
            return true;
    }
    return false;                    // 快指针走到 NULL，无环
}

// LeetCode 142. 环形链表 II：返回环的入口结点
// 思路：先找相遇点，再一个从头走、一个从相遇点走，相遇处即入口
struct ListNode* detectCycle(struct ListNode* head)
{
    struct ListNode* slow = head;
    struct ListNode* fast = head;
 
    // ① 判环，顺便记录相遇点
    while (fast != NULL && fast->next != NULL)
    {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast)
            break;                 // 相遇，跳出循环
    }
    // 无环：fast 走到了 NULL
    if (fast == NULL || fast->next == NULL)
        return NULL;
 
    // ② 一个指针从头开始，一个指针从相遇点开始，同步走一步
    struct ListNode* meet = fast;  // 相遇点
    struct ListNode* cur = head;
    while (cur != meet)
    {
        cur = cur->next;           // 从头走
        meet = meet->next;         // 从相遇点绕环走
    }
    return cur;                    // 相遇处就是环的入口
}

// List.h
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>
 
typedef int LTDataType;
 
typedef struct ListNode
{
    struct ListNode* next;   // 保存下一个结点的地址
    struct ListNode* prev;   // 保存前一个结点的地址
    LTDataType data;
} LTNode;
 
LTNode* LTInit(void);                        // 初始化，返回哨兵位
void LTDestroy(LTNode* phead);
void LTPrint(LTNode* phead);
bool LTEmpty(LTNode* phead);
void LTPushBack(LTNode* phead, LTDataType x);
void LTPopBack(LTNode* phead);
void LTPushFront(LTNode* phead, LTDataType x);
void LTPopFront(LTNode* phead);
void LTInsert(LTNode* pos, LTDataType x);    // 在 pos 之后插入
void LTErase(LTNode* pos);                   // 删除 pos 结点
LTNode* LTFind(LTNode* phead, LTDataType x);

// List.c
#include "List.h"
 
// 申请一个新结点
LTNode* BuyLTNode(LTDataType x)
{
    LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
    if (newnode == NULL)
    {
        perror("malloc fail");
        exit(1);
    }
    newnode->data = x;
    newnode->next = NULL;
    newnode->prev = NULL;
    return newnode;
}
 
// 初始化：创建哨兵位头结点（不存有效数据），首尾都指向自己
LTNode* LTInit(void)
{
    LTNode* phead = BuyLTNode(0);   // 哨兵位的数据无意义，随便给
    phead->next = phead;
    phead->prev = phead;
    return phead;
}
 
// 销毁：先释放所有有效结点，最后释放哨兵位
void LTDestroy(LTNode* phead)
{
    LTNode* cur = phead->next;
    while (cur != phead)            // 绕回哨兵位说明遍历完毕
    {
        LTNode* next = cur->next;   // 先保存后继
        free(cur);
        cur = next;
    }
    free(phead);                    // 最后释放哨兵位
}
 
// 打印：从第一个有效结点开始，绕回哨兵位结束
void LTPrint(LTNode* phead)
{
    LTNode* cur = phead->next;
    printf("phead<->");
    while (cur != phead)
    {
        printf("%d<->", cur->data);
        cur = cur->next;
    }
    printf("phead\n");
}
 
// 判断链表是否为空：只有哨兵位（自己指向自己）就是空
bool LTEmpty(LTNode* phead)
{
    return phead->next == phead;
}

// 在 pos 之后插入新结点（统一的插入接口）
void LTInsert(LTNode* pos, LTDataType x)
{
    LTNode* newnode = BuyLTNode(x);
    LTNode* posNext = pos->next;    // 先保存 pos 的后继
 
    pos->next = newnode;            // ① pos 指向新结点
    newnode->prev = pos;            // ② 新结点指回 pos
    newnode->next = posNext;        // ③ 新结点指向原后继
    posNext->prev = newnode;        // ④ 原后继指回新结点
}
 
// 尾插 = 在最后一个结点之后插入 = 在哨兵位之前插入
void LTPushBack(LTNode* phead, LTDataType x)
{
    LTInsert(phead->prev, x);       // phead->prev 就是最后一个结点
}
 
// 头插 = 在哨兵位之后插入
void LTPushFront(LTNode* phead, LTDataType x)
{
    LTInsert(phead, x);             // 插在哨兵位后面就是头插
}

// 删除 pos 结点（统一的删除接口）
void LTErase(LTNode* pos)
{
    assert(pos != NULL);            // pos 不能为空
    LTNode* prev = pos->prev;       // 前驱
    LTNode* next = pos->next;       // 后继
 
    prev->next = next;              // 前驱直接指向后继
    next->prev = prev;              // 后继指回前驱
    free(pos);                      // 释放 pos
}
 
// 尾删 = 删除最后一个结点 = 删除哨兵位的前一个
void LTPopBack(LTNode* phead)
{
    assert(!LTEmpty(phead));        // 空链表不能删
    LTErase(phead->prev);
}
 
// 头删 = 删除哨兵位的后一个
void LTPopFront(LTNode* phead)
{
    assert(!LTEmpty(phead));
    LTErase(phead->next);
}
 
// 查找
LTNode* LTFind(LTNode* phead, LTDataType x)
{
    LTNode* cur = phead->next;
    while (cur != phead)            // 绕回哨兵位结束
    {
        if (cur->data == x)
            return cur;
        cur = cur->next;
    }
    return NULL;
}