已知非空线性链表由 list 指出, 链结点的构造为 (data,next)。写 - 算法, 将链表中数据域值最小的那个链结点移到链表的最前面。要求: 不得额外申请新的链结点

2023-04-24
湖南
本文字数：635 字
阅读完需：约 2 分钟

们可以在遍历链表的时候记录下整个链表中的最小值和对应的结点位置。然后将这个最小值所在的节点移到链表的最前面即可。具体的步骤如下：

定义两个指针，分别是 cur 和 min。cur 用于遍历整个链表，min 用于记录当前链表中的最小值所在的结点。
从链表的第二个结点开始遍历，将 cur 指针依次指向下一个结点。
比较 cur 结点中保存的值和 min 结点中保存的值，如果 cur 结点的值较小，则更新 min 指针为当前的 cur 结点。
遍历完整个链表后，将最小值所在的结点移到链表的最前面，可以采用交换链表结点值的方法来实现。

以下是具体的 C 语言代码实现：

void moveMinToFront(ListNode* list) {    if (list == NULL || list->next == NULL) {        return;    }    ListNode *cur = list->next;    ListNode *min = cur;    ListNode *pre = list;    // 找到整个链表中数据域最小的那个结点    while (cur != NULL) {        if (cur->data < min->data) {            min = cur;        }        pre = cur;        cur = cur->next;    }    // 如果链表中最小值已经在头结点，则不需要交换    if (min == list->next) {        return;    }    // 将最小值结点移到链表最前面    pre->next = min->next;    min->next = list->next;    list->next = min;    // 交换最小值结点和头结点的data值    int temp = list->next->data;    list->next->data = list->data;    list->data = temp;}