一、題目描述
????????已知線性鏈表由list指出，鏈節(jié)點(diǎn)的構(gòu)造為（data,next），請(qǐng)寫一個(gè)算法站辉，將鏈表中數(shù)據(jù)域值最小的那個(gè)節(jié)點(diǎn)移動(dòng)到鏈表的最前面。（不能申請(qǐng)額外的節(jié)點(diǎn)）（更好的閱讀體驗(yàn)，請(qǐng)?jiān)L問程序員在旅途）
二饰剥、分析解答
????????主要解題思路就是狸相，遍歷鏈表，找到最小的那個(gè)節(jié)點(diǎn)min捐川，以及該節(jié)點(diǎn)的前驅(qū)pre_min，然后將其移到鏈表的最前面逸尖。
????????值得注意的是古沥，由于節(jié)點(diǎn)結(jié)構(gòu)要求的是單向單鏈表，因此娇跟，如果要移動(dòng)min岩齿，必須要找到他的前驅(qū)。如果是雙向鏈表苞俘，就可以不用記錄前驅(qū)結(jié)點(diǎn)了盹沈。
int move_min_to_first(PNode head){
PNode pre_p = head->next, p = pre_p->next;
//將最小的元素節(jié)點(diǎn)及其前驅(qū)記錄下來(lái)
PNode pre_min = head, min = pre_p;
//判斷鏈表是否為空
if(head == NULL || head->next == NULL){
return -1;
}
//遍歷鏈表，尋找最小元素節(jié)點(diǎn)
while(p){
if(min->data > p->data){
pre_min = pre_p;
min = p;
}
pre_p = p;
p = p->next;
}
//移動(dòng)到鏈表的最前面
pre_min->next = min->next;
min->next = head->next;
head->next = min;
return 1;
}
????完整可執(zhí)行程序代碼如下：
#include<stdio.h>
#include<stdlib.h>
typedef struct node{
int data;
struct node *next;
}Node,*PNode;
/*
方法思路：
遍歷鏈表吃谣，找到其中最小的元素節(jié)點(diǎn)及其前驅(qū)結(jié)點(diǎn)乞封，然后將最小的節(jié)點(diǎn)放置在鏈表最前面。
返回值：
-1 鏈表為空岗憋，無(wú)法尋找肃晚；
0 查找失敗仔戈；
1查找成功关串。
*/
int move_min_to_first(PNode head){
PNode pre_p = head->next, p = pre_p->next;
//將最小的元素節(jié)點(diǎn)及其前驅(qū)記錄下來(lái)
PNode pre_min = head, min = pre_p;
//判斷鏈表是否為空
if(head == NULL || head->next == NULL){
return -1;
}
//遍歷鏈表，尋找最小元素節(jié)點(diǎn)
while(p){
if(min->data > p->data){
pre_min = pre_p;
min = p;
}
pre_p = p;
p = p->next;
}
//移動(dòng)到鏈表的最前面
pre_min->next = min->next;
min->next = head->next;
head->next = min;
return 1;
}
//頭插法建立帶有頭結(jié)點(diǎn)的單鏈表
PNode creat_list(){
//申請(qǐng)頭結(jié)點(diǎn)
PNode head = (PNode)malloc(sizeof(Node));
head->next = NULL;
scanf("%d",&(head->data)); // 頭結(jié)點(diǎn)的數(shù)據(jù)域可以存放總結(jié)點(diǎn)數(shù)
//新增元素
PNode p = NULL;
int i;
for(i=0;i<(head->data);i++){
p = (PNode)malloc(sizeof(Node));
scanf("%d",&(p->data));
//這是頭插法的關(guān)鍵所在
p->next = head->next;
head->next = p;
}
return head;
}
void print_list(PNode head){
PNode p = head->next;
while(p){
printf("p->data: %d \t",p->data);
p = p->next;
}
printf("\n");
}
int main(){
PNode head = creat_list();
print_list(head);
move_min_to_first(head);
print_list(head);
return 0;
}
