单链表全部实现（绝对史上最完整附例题）

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 typedef struct LinkNode
  4 {
  5     int data;
  6     LinkNode* next;
  7 }LinkNode;
  8 LinkNode *InitList()   //创建空的单链表
  9 {
 10     LinkNode *L = (LinkNode*)malloc(sizeof(LinkNode));
 11     L->next = NULL;
 12     return L;
 13 }
 14 void initLinkList(LinkNode *L)//尾插法插入数据
 15 {
 16     LinkNode *current = (LinkNode *)malloc(sizeof(LinkNode));
 17     L->next = current;
 18     printf("请输入结点数据（-1退出）");
 19     int tmp = 0;
 20     scanf("%d",&tmp);
 21     current->data=tmp;
 22     while (1)
 23     {
 24         scanf("%d", &tmp);
 25         if (tmp == -1)
 26         {
 27             break;
 28         }
 29         LinkNode *node = (LinkNode *)malloc(sizeof(LinkNode));
 30         node->next = NULL;
 31         node->data = tmp;
 32         current->next = node;//建立连接
 33         current = node;//更新
 34     }
 35 }
 36 
 37 int printLinkList(LinkNode* pHeader)//依次输出当前链表每个元素
 38 {
 39     if (pHeader == NULL)
 40     {
 41         return 0;
 42     }
 43     if (pHeader->next == NULL)
 44     {
 45         printf("当前链表为空！
");
 46     }
 47     LinkNode* cur = pHeader->next;
 48     int num = 1;
 49     while (cur!=NULL)
 50     {
 51         printf("第%d个结点: %d  ", num, cur->data);
 52         cur = cur->next;
 53         num++;
 54     }
 55     cout<<'
';
 56     return 0;
 57 }
 58 int getLengthLinkList(LinkNode* pHeader)//输出链表的长度
 59 {
 60     if (pHeader == NULL)
 61     {
 62         return 0;
 63     }
 64     LinkNode* cur = pHeader;
 65     int length = 0;
 66     while (cur->next != NULL)
 67     {
 68         cur = cur->next;
 69         length++;
 70     }
 71     return length;
 72 }
 73 
 74 int printLinkListnumber(LinkNode* pHeader,int n)//输出位置n的数字
 75 {
 76     if (pHeader == NULL)
 77     {
 78         return 0;
 79     }
 80     if (pHeader->next == NULL)
 81     {
 82         printf("当前链表为空！
");
 83     }
 84     LinkNode* cur = pHeader->next;
 85     int num = 1;
 86     while (cur!=NULL)
 87     {
 88         if(num==n)
 89         {
 90             printf("第%d个结点: %d
", num, cur->data);
 91             break;
 92         }
 93         cur = cur->next;
 94         num++;
 95     }
 96     return 0;
 97 }
 98 
 99 int printLinkListvalue(LinkNode* pHeader,int val)//输出值为n的元素位置
100 {
101     if (pHeader == NULL)
102     {
103         return 0;
104     }
105     if (pHeader->next == NULL)
106     {
107         printf("当前链表为空！
");
108     }
109     LinkNode* cur = pHeader->next;
110     int num = 1;
111     while (cur!=NULL)
112     {
113         if(cur->data==val)
114         {
115             printf("值为%d的元素位于第%d个节点里
", cur->data, num);
116             break;
117         }
118         cur = cur->next;
119         num++;
120     }
121     return 0;
122 }
123 
124 //loc 插入到链表的第几个位置，从1开始 loc <=1 放在第一个位置 ，超过结点最后一个位置放在尾结点
125 int insertPositionLinkList(LinkNode* pHeader,int loc, int val)
126 {
127     if (pHeader == NULL)
128     {
129         return 0;
130     }
131     LinkNode* cur = pHeader;
132     int i = 1;
133     while (cur->next!=NULL && i<loc)
134     {
135         i++;
136         cur = cur->next;
137     }
138     //cur 为插入元素的前驱结点
139     LinkNode* newNode = (LinkNode*)malloc(sizeof(LinkNode));
140     newNode->data = val;
141     newNode->next = cur->next;
142     cur->next = newNode;
143     return 1;
144 }
145 //删除结点
146 int deleteLinkList(LinkNode* pHeader,int val)
147 {
148     if (pHeader == NULL)
149     {
150         return 0;
151     }
152     LinkNode* pre = pHeader;
153     LinkNode* cur = pHeader->next;
154     while (cur != NULL)
155     {
156         if (cur->data == val)
157         {
158             break;
159         }
160         pre = pre->next;
161         cur = cur->next;
162     }
163     if (cur != NULL)
164     {
165         pre->next = cur->next;
166         free(cur);
167         cur = NULL;
168     }
169     return 1;
170 }
171 //清空链表 保留头结点
172 int clearLinkList(LinkNode* pHeader)
173 {
174     if (pHeader == NULL)
175     {
176         return 0;
177     }
178     LinkNode* cur = pHeader->next;
179     while (cur != NULL)
180     {
181         LinkNode* next = cur->next;
182         free(cur);
183         cur = next;
184     }
185     pHeader->next = NULL;
186     return 1;
187 }
188 //销毁链表
189 int destroyLinkList(LinkNode* pHeader)
190 {
191     if (pHeader == NULL)
192     {
193         return 0;
194     }
195     clearLinkList(pHeader);
196     free(pHeader);
197     return 1;
198 }
199 //删除第loc位置的元素
200 int delPositionLinkList(LinkNode* pHeader, int loc)
201 {
202     if (pHeader == NULL || loc < 1)
203     {
204         cout<<"不可以！"<<endl;
205         return 0;
206     }
207     LinkNode* cur = pHeader;
208     int i = 1;
209     while (cur->next != NULL&&i<loc)
210     {
211         i++;
212         cur = cur->next;
213     }
214     //cur 为删除元素的前驱结点
215     if (i == loc && cur->next!=NULL)
216     {
217         LinkNode* del = cur->next;
218         cur->next = del->next;
219         free(del);
220         del = NULL;
221         return 1;
222     }
223     return 0;
224 }
225 //链表反转
226 int reverseLinkList(LinkNode* pHeader)
227 {
228     if (pHeader == NULL)
229     {
230         return 0;
231     }
232     LinkNode* pre = NULL;
233     LinkNode* cur = pHeader->next;
234     LinkNode* next = NULL;
235     while (cur !=NULL)
236     {
237         //保存当前节点的下一个结点
238         next = cur->next;
239         //将当前节点的next域指向前一个结点
240         cur->next = pre;
241 
242         //pre、cur 往后移动
243         pre = cur;
244         cur = next;
245     }
246     //循环结束 pre 指向最后一个结点，将头结点指向 它
247     pHeader->next = pre;
248     return 1;
249 }
250 
251 int main()
252 {
253     LinkNode* tmp;
254     int x,y;
255     int menu = 0;
256         printf("-------------------菜单--------------------
");
257         printf("---1、初始化链表---------------------------
");
258         printf("---2、一次采用尾插法插入a、b、c、d、e元素--
");
259         printf("---3、输出单链表；-------------------------
");
260         printf("---4、判断单链表是否为空并输出单链表长度---
");
261         printf("---5、输出单链表的第3个元素----------------
");
262         printf("---6、输出元素d的位置----------------------
");
263         printf("---7、在第4个元素位置上插入f元素-----------
");
264         printf("---8、输出插入后的单链表-------------------
");
265         printf("---9、删除单链表中的第2个元素；------------
");
266         printf("---10、输出删除后的单链表；----------------
");
267         printf("---11、单链表“原地”逆转，------------------
");
268         printf("---12、输出逆转后的单链表；----------------
");
269         printf("---0、退出---------------------------------
");
270     while (1)
271     {
272         printf("请输入:");
273         scanf("%d",&menu);
274         if (menu == 0)
275         {
276             break;
277         }
278         switch (menu)
279         {
280         case 1:
281             tmp=InitList();
282             cout<<"初始化链表成功"<<endl;
283             break;
284         case 2:
285             initLinkList(tmp);
286             cout<<"成功"<<endl;
287             break;
288         case 3:
289             printLinkList(tmp);
290             break;
291         case 4:
292             cout<<"当前链表长度为："<<getLengthLinkList(tmp)<<endl;
293             break;
294         case 5:
295             cout<<"请输入你要查询元素的位置";
296             scanf("%d",&x);
297             printLinkListnumber(tmp,x);
298             break;
299         case 6:
300             cout<<"请输入你要查询元素的值";
301             scanf("%d",&x);
302             printLinkListvalue(tmp,x);
303             break;
304         case 7:
305             cout<<"请输入你要插入的元素以及它位置";
306             scanf("%d %d",&x,&y);
307             insertPositionLinkList(tmp,x,y);
308             break;
309         case 8:
310             printLinkList(tmp);
311             break;
312         case 9:
313             cout<<"请输入你要删除元素的位置"<<endl;
314             scanf("%d",&x);
315             delPositionLinkList(tmp,x);
316             break;
317         case 10:
318             printLinkList(tmp);
319             break;
320         case 11:
321             reverseLinkList(tmp);
322             break;
323         case 12:
324             printLinkList(tmp);
325             break;
326         default:
327             break;
328         }
329 
330     }
331     return 0;
332 }

好像就是以前弄得作业

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 typedef struct LinkNode
  4 {
  5     int data;
  6     LinkNode* next;
  7 } LinkNode;
  8 LinkNode *InitList()   //创建空的单链表
  9 {
 10     LinkNode *L = (LinkNode*)malloc(sizeof(LinkNode));
 11     L->next = NULL;
 12     return L;
 13 }
 14 void initLinkList(LinkNode *L)//尾插法插入数据
 15 {
 16     LinkNode *current = (LinkNode *)malloc(sizeof(LinkNode));
 17     L->next = current;
 18     printf("请输入结点数据（-1退出）");
 19     int tmp = 0;
 20     scanf("%d",&tmp);
 21     current->data=tmp;
 22     while (scanf("%d",&tmp)&&tmp!=-1)
 23     {
 24         LinkNode *node = (LinkNode *)malloc(sizeof(LinkNode));
 25         node->next = NULL;
 26         node->data = tmp;
 27         current->next = node;//建立连接
 28         current = node;//更新
 29     }
 30 }
 31 
 32 int printLinkList(LinkNode* pHeader,int x)//依次输出当前链表每个元素
 33 {
 34     if (pHeader == NULL)
 35     {
 36         return 0;
 37     }
 38     if (pHeader->next == NULL)
 39     {
 40         printf("当前链表为空！
");
 41     }
 42     LinkNode* cur = pHeader->next;
 43     cout<<"当前链表("<<x<<")存放的元素依次为："<<endl;
 44     while (cur!=NULL)
 45     {
 46         cout<<cur->data<<' ';
 47         cur = cur->next;
 48     }
 49     cout<<'
';
 50     return 0;
 51 }
 52 void Union(LinkNode *a,LinkNode *b,LinkNode *c)
 53 {
 54     LinkNode *current = (LinkNode *)malloc(sizeof(LinkNode));
 55     c->next = current;
 56     LinkNode *pa = a->next;
 57     current->data=pa->data;
 58     pa=pa->next;
 59     while (pa!=NULL)
 60     {
 61         LinkNode *node = (LinkNode *)malloc(sizeof(LinkNode));
 62         node->next = NULL;
 63         node->data = pa->data;
 64         pa=pa->next;
 65         current->next = node;//建立连接
 66         current = node;//更新
 67     }
 68     LinkNode *pb = b->next;
 69     while(pb!=NULL)
 70     {
 71         pa=c->next;
 72         while(pa!=NULL)
 73         {
 74             if(pb->data==pa->data)
 75             {
 76                 break;
 77             }
 78             pa=pa->next;
 79         }
 80         if(pa==NULL)
 81         {
 82             LinkNode *node = (LinkNode *)malloc(sizeof(LinkNode));
 83             node->next = NULL;
 84             node->data = pb->data;
 85             current->next = node;//建立连接
 86             current = node;
 87         }
 88         pb=pb->next;
 89     }
 90 }
 91 void Intersection(LinkNode *a,LinkNode *b,LinkNode *c)
 92 {
 93     LinkNode *current = (LinkNode *)malloc(sizeof(LinkNode));
 94     c->next = current;
 95     LinkNode *pa;
 96     LinkNode *pb = b->next;
 97     bool flag=0;
 98     while(pb!=NULL)
 99     {
100         pa=a->next;
101         while(pa!=NULL)
102         {
103             if(pb->data==pa->data)
104             {
105                 if(flag==0)
106                 {
107                     current->data=pb->data;
108                     flag=1;
109                 }
110                 else
111                 {
112                     LinkNode *node = (LinkNode *)malloc(sizeof(LinkNode));
113                     node->next = NULL;
114                     node->data = pb->data;
115                     current->next = node;//建立连接
116                     current = node;
117                 }
118             }
119             pa=pa->next;
120         }
121         pb=pb->next;
122     }
123 }
124 void destroyLinkList(LinkNode* L)
125 {
126     LinkNode *pre,*p;
127     pre=L;//头节点
128     p=L->next;
129     free(pre);
130     while(p!=NULL)
131     {
132         pre=p;
133         p=p->next;
134         free(pre);
135     }
136     free(p);
137 }
138 int main()
139 {
140     LinkNode* tmp1,*tmp2,*tmp3;
141     int x,y;
142     int menu = 0;
143     printf("-------------------菜单----------------------
");
144     printf("---1、初始化链表(1)--------------------------
");
145     printf("---2、一次采用尾插法插入元素并输出单链表(1)--
");
146     printf("---3、初始化链表(2)--------------------------
");
147     printf("---4、一次采用尾插法插入元素并输出单链表(2)--
");
148     printf("---5、求单链表a、b的并集并输出最终的结果---
");
149     printf("---6、求单链表a、b的交集并输出最终的结果---
");
150     printf("---0、退出---------------------------------
");
151     while (1)
152     {
153         printf("请输入:");
154         scanf("%d",&menu);
155         if (menu == 0)
156         {
157             break;
158         }
159         switch (menu)
160         {
161         case 1:
162             tmp1=InitList();
163             cout<<"初始化链表(1)成功"<<endl;
164             break;
165         case 2:
166             initLinkList(tmp1);
167             cout<<"成功"<<endl;
168             printLinkList(tmp1,1);
169             break;
170         case 3:
171             tmp2=InitList();
172             cout<<"初始化链表(2)成功"<<endl;
173             break;
174         case 4:
175             initLinkList(tmp2);
176             cout<<"成功"<<endl;
177             printLinkList(tmp2,2);
178             break;
179         case 5:
180             tmp3=InitList();
181             Union(tmp1,tmp2,tmp3);
182             printLinkList(tmp3,3);
183             destroyLinkList(tmp3);
184             break;
185         case 6:
186             tmp3=InitList();
187             Intersection(tmp1,tmp2,tmp3);
188             printLinkList(tmp3,3);
189             destroyLinkList(tmp3);
190             break;
191         default:
192             break;
193         }
194 
195     }
196     return 0;
197 }

题目：

又回到最初的起点

 1 class Solution {
 2 public:
 3     ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
 4         ListNode* head=new ListNode(-1);//存放结果的链表
 5         ListNode* h=head;//移动指针
 6         int sum=0;//每个位的加和结果
 7         bool carry=false;//进位标志
 8         while(l1!=NULL||l2!=NULL)
 9         {
10             sum=0;
11             if(l1!=NULL)
12             {
13                 sum+=l1->val;
14                 l1=l1->next;
15             }
16             if(l2!=NULL)
17             {
18                 sum+=l2->val;
19                 l2=l2->next;
20             }
21             if(carry)
22                 sum++;
23             h->next=new ListNode(sum%10);
24             h=h->next;
25             carry=sum>=10?true:false;
26         }
27         if(carry)
28         {
29             h->next=new ListNode(1);
30         }
31         return head->next;
32     }
33 };

单链表全部实现（绝对史上最完整 附例题）

单链表全部实现（绝对史上最完整附例题）