AB18-将带头结点单链表中值最小的结点移动到链表最前面
代码实现
| C |
|---|
| /**
* 将带头结点单链表中值最小的结点移动到链表最前面
* @param L 指向链表头结点的指针
* @return 移动成功返回true，链表为空返回false
*/
bool move(LinkList L) {
// 边界条件检查：空链表或只有一个头结点
if (L == NULL || L->next == NULL) {
return false;
}
// p指向当前结点的前驱（从头结点开始）
LinkList p = L;
// pos指向最小值结点的前驱结点
LinkList pos = L;
// 遍历链表查找最小值结点
while (p->next != NULL) {
// 如果当前结点的值小于已知最小值
if (p->next->data < pos->next->data) {
pos = p; // 更新最小值结点的前驱
}
p = p->next; // 继续向后查找
}
// 如果最小值结点已经在第一个位置，则无需移动
if (pos == L) {
return false; // 没有发生移动
}
// 将最小值结点移动到链表最前面
LinkList r = pos->next; // r指向要移动的最小值结点
pos->next = r->next; // 从原位置删除最小值结点
r->next = L->next; // 最小值结点指向原第一个数据结点
L->next = r; // 头结点指向最小值结点
return true; // 移动成功
}
|
算法执行流程图解
移动过程示例：
| Text Only |
|---|
| 原链表：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 = L->next → [2]→[5]
3. L->next = r → 头→[2]
移动后：L→[ ]→[2]→[5]→[8]→[3]→[7]→NULL
|
移动操作详细图解
| Text Only |
|---|
| 移动前：
L→[ ]→[A]→[B]→[C]→[D]→[E]→NULL
↑ ↑ ↑ ↑ ↑
pos r r->next
移动操作：
步骤1：断开最小值结点
L→[ ]→[A]→[C]→[D]→[E]→NULL [B]→[C]→[D]→[E]→NULL
↑ ↑ ↑
pos r r->next
步骤2：最小值结点指向原第一个结点
[B]→[A]→[C]→[D]→[E]→NULL
步骤3：头结点指向最小值结点
L→[ ]→[B]→[A]→[C]→[D]→[E]→NULL
|
复杂度分析
时间复杂度：O(n)
- 查找时间：需要遍历整个链表一次，O(n)
- 移动时间：常数时间O(1)
- 总体时间复杂度：O(n)
空间复杂度：O(1)
- 额外空间：只使用了常数个指针变量：
p、pos、r
- 无辅助空间：没有使用额外的数据结构
- 算法额外空间复杂度：O(1)
优化版本1：更清晰的逻辑和变量命名
| C |
|---|
| /**
* 优化版本1：更清晰的逻辑和变量命名
*/
bool move_Optimized1(LinkList L) {
// 边界检查
if (L == NULL || L->next == NULL) {
return false;
}
// 查找最小值结点的前驱
LinkList current = L;
LinkList 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;
}
// 执行移动操作
LinkList min_node = min_prev->next;
min_prev->next = min_node->next;
min_node->next = L->next;
L->next = min_node;
return true;
}
|
优化版本2：支持移动最大值结点
| C |
|---|
| /**
* 优化版本2：支持移动最大值结点
*/
bool move_extreme(LinkList L, bool move_min) {
if (L == NULL || L->next == NULL) {
return false;
}
LinkList current = L;
LinkList extreme_prev = L;
while (current->next != NULL) {
if (move_min) {
if (current->next->data < extreme_prev->next->data) {
extreme_prev = current;
}
} else {
if (current->next->data > extreme_prev->next->data) {
extreme_prev = current;
}
}
current = current->next;
}
if (extreme_prev == L) {
return false;
}
LinkList extreme_node = extreme_prev->next;
extreme_prev->next = extreme_node->next;
extreme_node->next = L->next;
L->next = extreme_node;
return true;
}
|
特殊情况处理：处理多个相同最小值的情况
| C |
|---|
| /**
* 增强版本：处理多个相同最小值的情况
*/
bool move_first_min(LinkList L) {
if (L == NULL || L->next == NULL) {
return false;
}
LinkList current = L;
LinkList 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;
}
// 移动第一个最小值结点
LinkList min_node = min_prev->next;
min_prev->next = min_node->next;
min_node->next = L->next;
L->next = min_node;
return true;
}
|
算法特点
核心思想：
1. 查找最小值：通过一次遍历找到最小值结点
2. 位置判断：判断最小值是否已在第一个位置
3. 结点移动：将最小值结点从原位置删除并插入到最前面
关键技巧：
- 前驱指针：使用前驱指针便于删除操作
- 三步移动：
1. 断开原连接
2. 建立新连接（最小值结点指向原第一个结点）
3. 更新头结点连接
与删除最小值的区别：
| 操作 |
删除最小值 |
移动最小值 |
| 结果 |
最小值消失 |
最小值移到前面 |
| 链表长度 |
减少1 |
不变 |
| 应用场景 |
清理数据 |
重新排序 |
易错点分析：
1. 边界条件：空链表和单结点链表的处理
2. 位置判断：最小值已在首位时的特殊情况
3. 指针操作：移动操作中的指针重连顺序
这种算法在实际应用中很有用，比如实现优先级调整、热点数据前置等场景。