原创内容，转载请注明原文网址：http://homeqin.cn/a/wenzhangboke/jishutiandi/2018/1013/75.html
今天常州手机App培训中心幻天网络带来的算法技巧主要是单链表的一些常见操作：像创建链表，删除结点，插入结点，链表逆序，按大小排序等
1 #include <iostream>
2 using namespace std;
3
4 struct Node
5 {
6 int val;
7 Node *next;
8 Node(int x) :val(x), next(nullptr){}
9 };
10
11 //创建带有头结点的单链表
12 void Create(Node *head)
13 {
14 int n;
15 Node *p(head), *q;
16 cout << "请输入元素个数及相应数据:";
17 cin >> n;
18 while (n--)
19 {
20 int value;
21 cin >> value;
22 q = new Node(value);
23 q->next = nullptr;
24 p->next = q;
25 p = q;
26 }
27 }
28
29 //获得链表长度
30 int GetSize(Node *head)
31 {
32 int num = 0;
33 Node *p = head->next;
34 while (p)
35 {
36 num++;
37 p = p->next;
38 }
39 return num;
40 }
41 //输出链表元素
42 void Print(Node *head)
43 {
44 Node *p = head->next;
45 while (p)
46 {
47 cout << p->val << ' ';
48 p = p->next;
49 }
50 }
51
52 //删除值为x的结点
53 void Delete(Node *head, int x)
54 {
55 Node *p(head), *q;
56 while (p->next && p->next->val != x)
57 {
58 p = p->next;
59 }
60 if (p->next)
61 {
62 q = p->next;
63 p->next = q->next;
64 delete[] q;
65 }
66 else
67 {
68 cout << "链表不存在值为" << x << "的结点" << endl;
69 }
70 }
71
72 //链表逆序
73 void Reverse(Node *head)
74 {
75 Node *p(head->next), *q(head->next);
76 head->next = nullptr;
77 while (p)
78 {
79 q = q->next;
80 p->next = head->next;
81 head->next = p;
82 p = q;
83 }
84 }
85
86 //在升序链表中插入结点使之仍然有序
87 void Insert(Node *head, Node *t)
88 {
89 Node *p(head);
90 while (p->next && p->next->val < t->val)
91 {
92 p = p->next;
93 }
94 t->next = p->next;
95 p->next = t;
96 }
97 //按升序排列
98 void Sort(Node *head)
99 {
100 Node *p, *q;
101 p = head->next;
102 head->next = nullptr;
103 while (p)
104 {
105 q = p;
106 p = p->next;
107 q->next = nullptr;
108 Insert(head, q);
109 }
110 }
111
112 void Tips()
113 {
114 cout << "\n请按键选择相应操作" << endl;
115 cout << "-------------------------" << endl;
116 cout << "1.输出链表" << endl;
117 cout << "2.删除链表某一结点" << endl;
118 cout << "3.链表逆序" << endl;
119 cout << "4.按升序排列" << endl;
120 cout << "-------------------------" << endl;
121 }
122 int main()
123 {
124 Node *head = new Node(0);
125 head->next = nullptr;
126 Create(head);
127 Tips();
128 char c;
129 while (cin >> c)
130 {
131 switch (c)
132 {
133 case '1':
134 Print(head);
135 break;
136 case'2':
137 int valToDelete;
138 cout << "请输入要删除结点的值:";
139 cin >> valToDelete;
140 Delete(head, valToDelete);
141 Print(head);
142 break;
143 case'3':
144 Reverse(head);
145 Print(head);
146 break;
147 case '4':
148 Sort(head);
149 Print(head);
150 break;
151 default:
152 break;
153 }
154 Tips();
155 }
156
157 }
测试结果：
上篇：上一篇：单链表逆序的几种方法
下篇：下一篇：线性表实现简单vector
