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

快来打我* 2023-02-20 03:25 10阅读 0赞

### 一、题目描述 ###

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

### 二、分析解答 ###

主要解题思路就是，遍历链表，找到最小的那个节点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;
      
      }

[Link 1]: https://www.meijindong.top/posts/1679559589.html