AB19-链表结点基础综合应用

## 对带头结点的正整数单链表执行特定操作： ## * 1. 找出最小值结点（非最后一个且唯一） ## * 2. 若该数值是奇数，将其与后继结点交换 ## * 3. 若该数值是偶数，则删除其后继结点

代码实现

/**
 * 对带头结点的正整数单链表执行特定操作：
 * 1. 找出最小值结点（非最后一个且唯一）
 * 2. 若该数值是奇数，将其与后继结点交换
 * 3. 若该数值是偶数，则删除其后继结点
 * @param L 指向链表头结点的指针
 * @return 操作成功返回true，无法操作返回false
 */
bool func(LinkList L) {
    // 边界条件检查：空链表或结点数少于2个
    if (L == NULL || L->next == NULL || L->next->next == NULL) {
        return false;
    }

    // p指向当前结点的前驱（从头结点开始）
    LNode* p = L;

    // pos指向最小值结点的前驱结点
    LNode* pos = L;

    // 遍历链表查找最小值结点
    while (p->next != NULL) {
        // 如果当前结点的值小于已知最小值
        if (p->next->data < pos->next->data) {
            pos = p;  // 更新最小值结点的前驱
        }
        p = p->next;  // 继续向后查找
    }

    // 检查最小值结点是否为最后一个结点
    if (pos->next->next == NULL) {
        return false;  // 最小值结点是最后一个，无法操作
    }

    // 获取最小值结点u和其后继结点r
    LNode* u = pos->next;    // 最小值结点
    LNode* r = u->next;      // 最小值结点的后继

    // 断开最小值结点与其后继的连接
    u->next = r->next;

    // 根据最小值的奇偶性执行不同操作
    if (pos->next->data % 2 == 0) {
        // 最小值是偶数：删除后继结点r
        free(r);
    } else {
        // 最小值是奇数：将后继结点r与最小值结点u交换位置
        r->next = pos->next;   // r指向u
        pos->next = r;         // pos指向r（r在前，u在后）
    }

    return true;  // 操作成功
}

算法执行流程图解

奇数情况示例：

原链表：L→[ ]→[5]→[3]→[8]→[2]→[7]→NULL

查找最小值：
找到最小值3（位置pos指向[5]）

操作前：L→[ ]→[5]→[3]→[8]→[2]→[7]→NULL
              ↑    ↑    ↑
             pos   u    r

操作步骤：
1. u->next = r->next  → [3]→[2]
2. 最小值3是奇数
3. r->next = u        → [8]→[3]
4. pos->next = r      → [5]→[8]

操作后：L→[ ]→[5]→[8]→[3]→[2]→[7]→NULL

偶数情况示例：

原链表：L→[ ]→[5]→[4]→[8]→[2]→[7]→NULL

查找最小值：
找到最小值4（位置pos指向[5]）

操作前：L→[ ]→[5]→[4]→[8]→[2]→[7]→NULL
              ↑    ↑    ↑
             pos   u    r

操作步骤：
1. u->next = r->next  → [4]→[2]
2. 最小值4是偶数
3. 删除结点r=[8]
4. free(r)

操作后：L→[ ]→[5]→[4]→[2]→[7]→NULL

操作详细图解

奇数交换操作：

操作前：
L→[ ]→[A]→[奇数]→[B]→[C]→NULL
     ↑        ↑     ↑
    pos      u     r

步骤1：断开连接
L→[ ]→[A]→[奇数]→[C]→NULL    [B]→[C]→NULL
     ↑        ↑              ↑
    pos      u              r

步骤2：交换位置
L→[ ]→[A]→[B]→[奇数]→[C]→NULL
     ↑     ↑        ↑
    pos    r       u

偶数删除操作：

操作前：
L→[ ]→[A]→[偶数]→[B]→[C]→NULL
     ↑        ↑     ↑
    pos      u     r

步骤1：断开连接
L→[ ]→[A]→[偶数]→[C]→NULL    [B]→[C]→NULL
     ↑        ↑              ↑
    pos      u              r

步骤2：删除r
L→[ ]→[A]→[偶数]→[C]→NULL

复杂度分析

时间复杂度：O(n)

• 查找时间：需要遍历整个链表一次，O(n)
• 操作时间：常数时间O(1)
• 总体时间复杂度：O(n)

空间复杂度：O(1)

• 额外空间：只使用了常数个指针变量：p、pos、u、r
• 无辅助空间：没有使用额外的数据结构
• 算法额外空间复杂度：O(1)

优化版本：添加边界检查和更清晰的逻辑

/**
 * 优化版本：添加边界检查和更清晰的逻辑
 */
bool func_Optimized(LinkList L) {
    // 边界检查：确保至少有3个结点（头结点+2个数据结点）
    if (!L || !L->next || !L->next->next) {
        return false;
    }

    // 查找最小值结点的前驱
    LinkList current = L;
    LinkList min_prev = L;

    while (current->next) {
        if (current->next->data < min_prev->next->data) {
            min_prev = current;
        }
        current = current->next;
    }

    // 检查最小值结点是否为最后一个
    if (!min_prev->next->next) {
        return false;
    }

    // 获取相关结点
    LinkList min_node = min_prev->next;
    LinkList next_node = min_node->next;

    // 断开连接
    min_node->next = next_node->next;

    // 根据奇偶性执行操作
    if (min_node->data % 2 == 0) {
        // 偶数：删除后继结点
        free(next_node);
    } else {
        // 奇数：交换结点位置
        next_node->next = min_node;
        min_prev->next = next_node;
    }

    return true;
}

算法特点

核心思想： 1. 查找最小值：遍历链表找到最小值结点 2. 边界检查：确保最小值结点不是最后一个 3. 分类操作：根据最小值的奇偶性执行不同操作

关键操作： - 奇数操作：结点交换（不是数据交换） - 偶数操作：删除后继结点 - 通用操作：断开最小值结点与其后继的连接

创新点： - 结合了查找、判断、分类操作的综合性算法 - 区分结点交换和数据交换的概念 - 根据数值特性执行不同链表操作

应用场景： - 数据预处理和清洗 - 基于数值特性的链表结构调整 - 复合条件的链表操作

这种算法体现了链表操作的灵活性和复杂性，是数据结构与算法设计中的经典案例。