C语言给定一个带头结点的单链表,写一个函数查找其最小值,并将最小值结点挪到链表的头部。 【输入形式】 链表L长度 链表L,以空格区分 【输出形式】 最小值 链表,以空格区分 【样例输入】 3 5 1 3 【样例输出】 1 1 5 3
时间: 2023-12-14 18:37:32 浏览: 77
以下是一份C语言代码,实现了题目要求的功能:
```c
#include<stdio.h>
#include<stdlib.h>
// 定义链表结构体
struct ListNode {
int val;
struct ListNode *next;
};
// 查找链表最小值,并将最小值结点挪到链表头部
struct ListNode* moveMinToHead(struct ListNode* head) {
if (head == NULL || head->next == NULL) {
return head;
}
struct ListNode *minPrev = NULL; // 最小值结点的前一个结点
struct ListNode *minNode = head; // 最小值结点
struct ListNode *prev = head; // 当前结点的前一个结点
struct ListNode *cur = head->next; // 当前结点
while (cur != NULL) {
if (cur->val < minNode->val) {
minPrev = prev;
minNode = cur;
}
prev = cur;
cur = cur->next;
}
if (minNode != head) {
minPrev->next = minNode->next;
minNode->next = head;
head = minNode;
}
return head;
}
// 创建链表
struct ListNode* createList(int* nums, int numsSize) {
struct ListNode* head = (struct ListNode*)malloc(sizeof(struct ListNode));
head->next = NULL;
struct ListNode* tail = head;
for (int i = 0; i < numsSize; i++) {
struct ListNode* node = (struct ListNode*)malloc(sizeof(struct ListNode));
node->val = nums[i];
node->next = NULL;
tail->next = node;
tail = tail->next;
}
return head;
}
// 打印链表
void printList(struct ListNode* head) {
struct ListNode* cur = head->next;
while (cur != NULL) {
printf("%d ", cur->val);
cur = cur->next;
}
}
// 释放链表
void freeList(struct ListNode* head) {
struct ListNode* cur = head;
while (cur != NULL) {
struct ListNode* tmp = cur;
cur = cur->next;
free(tmp);
}
}
int main() {
int n;
scanf("%d", &n);
int* nums = (int*)malloc(sizeof(int) * n);
for (int i = 0; i < n; i++) {
scanf("%d", &nums[i]);
}
struct ListNode* head = createList(nums, n);
head = moveMinToHead(head);
printList(head);
freeList(head);
free(nums);
return 0;
}
```
算法思路:
1. 定义4个指针变量:`minPrev`、`minNode`、`prev`、`cur`,分别表示最小值结点的前一个结点、最小值结点、当前结点的前一个结点、当前结点。
2. 初始化 `minPrev`、`minNode`、`prev`、`cur` 指向头结点的下一个结点。
3. 遍历整个链表,如果当前结点的值比最小值结点的值小,则更新 `minPrev` 和 `minNode`。
4. 如果最小值结点不在头结点,则将其从原来的位置删除,并插入到头结点后面。
5. 返回头结点。
时间复杂度:$O(n)$
空间复杂度:$O(1)$