链表实现插入排序

将一串整型范围内的数按升序输出。

数据输入样式

16
-53 -3 -54 74 48 18 -24 54 63 663 -9 9 19 -9999 0 789

用链表实现实例：

1）结构体定义

1 struct ListNode
2 {
3     int data;
4     ListNode *next;//结构体指针
5     ListNode *pre; //结构体指针    
6 };

2）建一个初始链表，整型最小值和整型最大值串成一个初始链表，n个数都将在这两个节点之间。

1     ListNode *headNode = new ListNode{ minN,NULL,NULL }; //建头节点 存minN最小值 
2     ListNode *tailNode = new ListNode{ maxN,NULL,NULL }; //建尾节点 存maxN最大值
3     
4     //建一个只有minN和maxN两个节点的链表，    
5     headNode->next= tailNode;
6     tailNode->pre =headNode;

3）寻找位置将n个新节点插入链表中

 1         //建立新的节点 
 2         cin>>d; 
 3         ListNode* newNode = new ListNode{ d,NULL,NULL  };
 4         
 5         //从头遍历链表，为新节点查找插入位置,新节点将会插入到当前节点的前面
 6         pNode=headNode;
 7         while(pNode->next!=NULL && pNode->data<=d ) pNode=pNode->next;
 8         
 9         //修改指针，实现插入操作 ，注意修改的顺序       
10         newNode->next=pNode;       // 新节点的next指向当前节点
11         newNode->pre=pNode->pre;   // 新节点的per指向当前节点的前一个节点
12 　　　　　pNode->pre->next=newNode;  // 修改前一个节点的next,使其指向新节点
13         pNode->pre=newNode;        // 修改当前节点的pre,使其指向新节点

 3）掐头去尾输出链表中的值

1     pNode=headNode->next;
2     while(pNode->next!=NULL){
3         cout<<pNode->data<<" ";
4         pNode=pNode->next;
5     }

完整代码：

 1 /*
 2 将一串整型范围内的数按升序输出。
 3 
 4 16
 5 -53 -3 -54 74 48 18 -24 54 63 663 -9 9 19 -9999 0 789 
 6 
 7 使用链表实现
 8 flatte@20230903
 9 */
10 
11 
12 #include<bits/stdc++.h>
13 using namespace std;
14 #define LL long long
15 
16 const int N = 1e5+10;
17 const int minN=INT_MIN;
18 const int maxN=INT_MAX;
19 int n,d; 
20 
21 struct ListNode
22 {
23     int data;
24     ListNode *next;//结构体指针
25     ListNode *pre; //结构体指针    
26 };
27 
28 
29 int main(){
30 
31     ListNode *headNode = new ListNode{ minN,NULL,NULL }; //建头节点 存minN最小值 
32     ListNode *tailNode = new ListNode{ maxN,NULL,NULL }; //建尾节点 存maxN最大值
33     
34     //建一个只有minN和maxN两个节点的链表，    
35     headNode->next= tailNode;
36     tailNode->pre =headNode;
37     
38     
39     //将n个数据插入到这个链表中 
40     ListNode *pNode; 
41   
42     cin>>n;
43     for (int i=1; i<=n; i++) {        
44         
45         //建立新的节点 
46         cin>>d; 
47         ListNode* newNode = new ListNode{ d,NULL,NULL  };
48         
49         //从头遍历链表，为新节点查找插入位置
50         pNode=headNode;
51         while(pNode->next!=NULL && pNode->data<=d ) pNode=pNode->next;
52         
53         //修改指针，实现插入操作        
54         newNode->next=pNode;
55         newNode->pre=pNode->pre;        
56         pNode->pre->next=newNode;
57         pNode->pre=newNode;
58 
59     }
60     
61     //掐头去尾输出链表中的值 
62     pNode=headNode->next;
63     while(pNode->next!=NULL){
64         cout<<pNode->data<<" ";
65         pNode=pNode->next;
66     }
67     
68     return 0;
69 }