寻找链表中值域最小的节点并移到链表的最前面

一、题目描述

        已知线性链表由list指出，链节点的构造为（data,next），请写一个算法，将链表中数据域值最小的那个节点移动到链表的最前面。（不能申请额外的节点）（更好的阅读体验，请访问程序员在旅途）

二、分析解答

        主要解题思路就是，遍历链表，找到最小的那个节点min，以及该节点的前驱pre_min，然后将其移到链表的最前面。
        值得注意的是，由于节点结构要求的是单向单链表，因此，如果要移动min，必须要找到他的前驱。如果是双向链表，就可以不用记录前驱结点了。

int move_min_to_first(PNode head){
　　PNode pre_p = head->next, p = pre_p->next;
　　//将最小的元素节点及其前驱记录下来
　　PNode pre_min = head, min = pre_p;
　　//判断链表是否为空
　　if(head == NULL || head->next == NULL){
　　　　return -1;
　　}
　　//遍历链表，寻找最小元素节点
　　while§{
　　　　if(min->data > p->data){
　　　　　　pre_min = pre_p;
　　　　　　min = p;
　　　　}
　　　　pre_p = p;
　　　　p = p->next;
　　}
　　//移动到链表的最前面
　　pre_min->next = min->next;
　　min->next = head->next;
　　head->next = min;
　　return 1;
}

    完整可执行程序代码如下：

#include<stdio.h>
#include<stdlib.h>

typedef struct node{
    

	int data;
	struct node *next;

}Node,*PNode;


/* 方法思路： 遍历链表，找到其中最小的元素节点及其前驱结点，然后将最小的节点放置在链表最前面。 返回值： -1 链表为空，无法寻找； 0 查找失败； 1查找成功。 */

int move_min_to_first(PNode head){
    

	PNode pre_p = head->next, p = pre_p->next;
    
	//将最小的元素节点及其前驱记录下来
	PNode pre_min = head, min = pre_p;

	//判断链表是否为空
	if(head == NULL || head->next == NULL){
    
	
		return -1;
	}

	//遍历链表，寻找最小元素节点
	while(p){
    
	
		if(min->data > p->data){
    
		
			pre_min = pre_p;
			min = p;
		
		}

		pre_p = p;
		p = p->next;

	}

	//移动到链表的最前面
	pre_min->next = min->next;
	min->next = head->next;
	head->next = min;

	return 1;

}

//头插法建立带有头结点的单链表
PNode creat_list(){
    
 
	//申请头结点
	PNode head = (PNode)malloc(sizeof(Node));
 
	head->next = NULL;
	scanf("%d",&(head->data)); // 头结点的数据域可以存放总结点数
 
	//新增元素
	PNode p =  NULL;
	int i;
	for(i=0;i<(head->data);i++){
    
	
		p = (PNode)malloc(sizeof(Node));
 
		scanf("%d",&(p->data));
		
		//这是头插法的关键所在
		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;
  
  }