avatar

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

一、题目描述

  已知线性链表由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(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;
}

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#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;

}

文章作者: IT之旅
文章链接: https://www.meijindong.top/posts/1679559589.html
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 程序员在旅途
打赏
  • 微信
    微信
  • 支付宝
    支付宝

评论