AB22-将带头结点双向链表中值最小的结点移动到链表最前面

代码实现

/**
 * 将带头结点双向链表中值最小的结点移动到链表最前面
 * @param L 指向双向链表头结点的指针
 * @return 移动成功返回true，最小值已在首位或链表为空返回false
 */
bool move(DinkList L) {
    // 边界条件检查：空链表或只有一个头结点
    if (L == NULL || L->next == NULL) {
        return false;
    }

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

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

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

    // 如果最小值结点已经在第一个位置，则无需移动
    if (pos == L) {
        return false;  // 没有发生移动
    }

    // 将最小值结点移动到链表最前面
    DinkList r = pos->next;        // r指向要移动的最小值结点

    // 1. 从原位置断开最小值结点
    pos->next = r->next;           // 前驱结点指向最小值结点的后继
    // 防止最后一个结点值最小的情况
    if (r->next != NULL) {
        r->next->prev = pos;       // 后继结点的前驱指向原前驱结点
    }

    // 2. 将最小值结点插入到链表最前面
    r->next = L->next;             // 最小值结点指向原第一个数据结点
    L->next->prev = r;             // 原第一个数据结点的前驱指向最小值结点
    L->next = r;                   // 头结点指向最小值结点
    r->prev = L;                   // 最小值结点的前驱指向头结点

    return true;  // 移动成功
}

算法执行流程图解

移动过程示例：

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

查找最小值过程：
p=L: p->next=[5], pos->next=[5]
p=[5]: p->next=[2], 2<5? 是 → pos=[5]
p=[2]: p->next=[8], 8<2? 否
p=[8]: p->next=[3], 3<2? 否
p=[3]: p->next=[7], 7<2? 否
p=[7]: p->next=NULL, 结束

找到：pos=[5]（最小值结点[2]的前驱）

移动操作：
移动前：L→[ ]↔[5]↔[2]↔[8]↔[3]↔[7]↔NULL
              ↑    ↑    ↑
             pos   r   r->next

移动步骤：
1. pos->next = r->next  → [5]→[8]
2. r->next->prev = pos  → [8]←[5]
3. r->next = L->next    → [2]→[5]
4. L->next->prev = r    → [5]←[2]
5. L->next = r          → 头→[2]
6. r->prev = L          → [2]←头

移动后：L→[ ]↔[2]↔[5]↔[8]↔[3]↔[7]↔NULL

关键操作详细图解

从原位置断开结点：

断开前：
L→[ ]↔[A]↔[最小值]↔[B]↔[C]↔NULL
     ↑        ↑        ↑
    pos      r      r->next

断开操作：
1. pos->next = r->next
   L→[ ]↔[A]→[B]↔[C]↔NULL    [最小值]→[B]↔[C]↔NULL

2. r->next->prev = pos (如果r->next存在)
   L→[ ]↔[A]↔[B]↔[C]↔NULL    [最小值]→[B]←[A] [C]↔NULL

插入到链表最前面：

插入前：
L→[ ]↔[A]↔[B]↔[C]↔NULL    [最小值]→[B]←[A] [C]↔NULL

插入操作：
1. r->next = L->next
   [最小值]→[A]↔[B]↔[C]↔NULL

2. L->next->prev = r
   [最小值]↔[A]↔[B]↔[C]↔NULL

3. L->next = r
   L→[ ]→[最小值]↔[A]↔[B]↔[C]↔NULL

4. r->prev = L
   L↔[ ]↔[最小值]↔[A]↔[B]↔[C]↔NULL

特殊情况处理

最后一个结点值最小：

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

移动前：L→[ ]↔[5]↔[8]↔[3]↔[2]↔NULL
                          ↑    ↑
                         pos   r

移动操作：
1. pos->next = r->next = NULL
   L→[ ]↔[5]↔[8]↔[3]↔NULL

2. r->next = L->next = [5]
   [2]→[5]↔[8]↔[3]↔NULL

3. L->next->prev = r = [2]
   [2]↔[5]↔[8]↔[3]↔NULL

4. L->next = r = [2]
   L→[ ]→[2]↔[5]↔[8]↔[3]↔NULL

5. r->prev = L = [ ]
   L↔[ ]↔[2]↔[5]↔[8]↔[3]↔NULL

复杂度分析

时间复杂度：O(n)

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

空间复杂度：O(1)

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

优化版本：更清晰的逻辑和变量命名

/**
 * 优化版本：更清晰的逻辑和变量命名
 */
bool move_Optimized(DinkList L) {
    // 边界检查
    if (L == NULL || L->next == NULL) {
        return false;
    }

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

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

    // 如果最小值已在第一个位置，无需移动
    if (min_prev == L) {
        return false;
    }

    // 执行移动操作
    DinkList min_node = min_prev->next;

    // 从原位置删除
    min_prev->next = min_node->next;
    if (min_node->next != NULL) {
        min_node->next->prev = min_prev;
    }

    // 插入到最前面
    min_node->next = L->next;
    L->next->prev = min_node;
    L->next = min_node;
    min_node->prev = L;

    return true;
}

双向链表移动与单向链表对比

操作	单向链表	双向链表
指针操作数	4个	6个
实现复杂度	相对简单	较复杂
安全性	需要更多边界检查	prev指针提供额外信息
调试难度	中等	较高

算法特点

核心思想： 1. 查找最小值：通过一次遍历找到最小值结点 2. 双向断链：正确处理prev和next指针 3. 双向连接：重新建立新的双向连接关系

关键技巧： - 边界处理：特别注意最后一个结点的特殊情况 - 指针操作顺序：避免断链和野指针 - 双向维护：同时维护前驱和后继指针

优势： - 双向链表的prev指针提供了更多的操作便利性 - 删除和插入操作更加直观 - 可以进行双向遍历验证

易错点： 1. 空指针检查：移动最后一个结点时r->next为NULL 2. 指针操作顺序：必须先断开再连接 3. 双向一致性：确保prev和next指针同时正确

这种算法展示了双向链表操作的复杂性和优势，是数据结构学习中的重要案例。