已知非空线性链表由list指出,链结点的构造为(data,link)。请写一算法,将链表中数据域值最小的那个链结点移到链表的最前面。
时间: 2023-04-25 11:04:39 浏览: 151
链表插入结点算法
算法如下:
1. 定义一个指针minNode,指向链表的第一个结点,用于记录当前最小值的结点。
2. 定义一个指针preMinNode,指向minNode的前一个结点,用于记录当前最小值结点的前一个结点。
3. 从链表的第二个结点开始遍历链表,比较每个结点的data域值与minNode的data域值的大小,如果小于minNode的data域值,则将minNode指向该结点,preMinNode指向minNode的前一个结点。
4. 如果minNode不是链表的第一个结点,则将preMinNode的link指向minNode的link,将minNode插入到链表的最前面,即将minNode的link指向链表的第一个结点,将list指向minNode。
5. 返回链表list。
代码如下:
```
Node* moveMinNodeToFront(Node* list) {
if (list == NULL || list->link == NULL) {
return list;
}
Node* minNode = list;
Node* preMinNode = NULL;
Node* p = list->link;
while (p != NULL) {
if (p->data < minNode->data) {
minNode = p;
preMinNode = list;
} else {
preMinNode = p;
}
p = p->link;
}
if (minNode != list) {
preMinNode->link = minNode->link;
minNode->link = list;
list = minNode;
}
return list;
}
```
阅读全文