0.单链表的增、删、改、查(无头指针)
1 #include <stdio.h>
2 #include<stdlib.h>
3 struct Node
4 {
5 int val;
6 Node * next;
7 };
8
9 Node* Node_Insert(Node* First,int val)
10 {
11 Node* p=(Node*)calloc(1,sizeof(Node));
12 p->val=val;
13 p->next=First;
14 First=p;
15 return First;
16 }
17
18 Node* Node_Delete(Node* First,int val)
19 {
20 Node* p = First;
21 Node* pre=NULL;
22 Node* tem=NULL;
23 int find=0;
24 while(p!=NULL)
25 {
26 if(p->val==val)
27 {
28 pre->next=p->next;
29 tem=p;
30 p=pre->next;
31 free(tem);
32 }
33 else
34 {
35 pre=p;
36 p=p->next;
37 }
38 }
39 return First;
40 }
41
42
43
44 Node* Node_Change(Node* First,int m,int n)
45 {
46 Node* p = First;
47 while(p!=NULL)
48 {
49 if(p->val==m)
50 {
51 p->val=n;
52 }
53 p=p->next;
54 }
55 return First;
56 }
57
58
59 int Node_Search(Node* First,int x)
60 {
61 Node* p = First;
62 int index=0;
63 while(p!=NULL)
64 {
65 ++index;
66 if(p->val==x)
67 break;
68 p=p->next;
69 }
70 if(p==NULL)
71 index=-1;
72 return index;
73 }
74
75
76 void order(Node* First)
77 {
78 Node* p=First;
79 while(p!=NULL)
80 {
81 printf("%d ",p->val);
82 p=p->next;
83 }
84 }
85
86
87 int main()
88 {
89 int n,i,tem,tem2;
90 while(printf("链表长度:")&&scanf("%d",&n)!=EOF)
91 {
92 getchar();
93 Node* First=NULL;
94 printf("请插入链表:");
95 for(i=0;i<n;i++)
96 {
97 scanf("%d",&tem);
98 First=Node_Insert(First,tem);
99 }
100 getchar();
101 printf("请输入删除的值:");
102 scanf("%d",&tem);
103 getchar();
104 First=Node_Delete(First,tem);
105 printf("删除后:\n");
106 order(First);
107 printf("\n");
108 printf("请输入修改前和修改后的值:");
109 scanf("%d %d",&tem,&tem2);
110 getchar();
111 First=Node_Change(First,tem,tem2);
112 printf("修改后:\n");
113 order(First);
114 printf("\n");
115 printf("请输入要查找的值:");
116 scanf("%d",&tem);
117 getchar();
118 tem2=Node_Search(First,tem);
119 if(tem2==-1) printf("没有这个数\n");
120 else printf("第%d个数\n",tem2);
121 }
122 return 0;
123 }
1 /*
2 struct ListNode {
3 int val;
4 struct ListNode *next;
5 ListNode(int x) :
6 val(x), next(NULL) {
7 }
8 };*/
9 class Solution {
10 public:
11 ListNode* ReverseList(ListNode* pHead) {
12 if(pHead!=NULL)
13 {
14 ListNode * pre=NULL;
15 ListNode * p=pHead;
16 ListNode * q=pHead->next;
17 while(q!=NULL)
18 {
19 p->next=pre;
20 pre=p;
21 p=q;
22 q=q->next;
23 }
24 p->next=pre;
25 return p;
26 }
27 return NULL;
28 }
29 };
*p,*q 指向第一个指针,p向前移动n次,q再跟着和p一直移动,等p移到末尾,q所指的就是倒是第n个元素
1 #include <stdio.h>
2 #include<stdlib.h>
3 struct Node
4 {
5 int val;
6 Node * next;
7 };
8
9 Node* Node_Insert(Node* First,int val)
10 {
11 Node* p=(Node*)calloc(1,sizeof(Node));
12 p->val=val;
13 p->next=First;
14 First=p;
15 return First;
16 }
17
18
19
20
21 void order(Node* First)
22 {
23 Node* p=First;
24 while(p!=NULL)
25 {
26 printf("%d ",p->val);
27 p=p->next;
28 }
29 }
30
31 int My_Node_Search(Node* First,int n)
32 {
33 int i;
34 Node* p,*q;
35 q=p=First;
36
37 if(First->next==NULL&&n==1) return 1;
38 if(First->next==NULL&&n>1) return -1;
39 if(n<=0) return -1;
40
41 for(i=0;i<n;i++)
42 {
43 if(p==NULL) return -1;
44 p=p->next;
45 }
46 while(p!=NULL)
47 {
48 p=p->next;
49 q=q->next;
50 }
51 return q->val;
52 }
53
54 int main()
55 {
56 int n,i,tem;
57 while(printf("链表长度:")&&scanf("%d",&n)!=EOF)
58 {
59 getchar();
60 Node* First=NULL;
61 printf("请插入链表:");
62 for(i=0;i<n;i++)
63 {
64 scanf("%d",&tem);
65 First=Node_Insert(First,tem);
66 }
67 getchar();
68 printf("链表为:");
69 order(First);
70 printf("\n");
71
72 printf("取倒数第几个数:");
73 while(scanf("%d",&tem)!=EOF)
74 {
75 tem=My_Node_Search(First,tem);
76 if(tem!=-1)
77 printf("值为%d\n",tem);
78 else printf("越界!\n");
79 printf("取倒数第几个数:");
80 }
81 }
82 return 0;
83 }
1 /*
2 struct ListNode {
3 int val;
4 struct ListNode *next;
5 ListNode(int x) :
6 val(x), next(NULL) {
7 }
8 };*/
9 class Solution {
10 public:
11 ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
12 {
13 ListNode* p=pHead1;
14 ListNode* q=pHead2;
15 ListNode* First=NULL;
16 ListNode* r=NULL;
17 if (p == NULL )
18 return q;
19 if (q == NULL )
20 return p;
21
22 if(p->val<q->val)
23 {
24 r=p;
25 p=p->next;
26 }
27 else
28 {
29 r=q;
30 q=q->next;
31 }
32
33 First=r;
34 while(p!=NULL&&q!=NULL)
35 {
36 if(p->val<q->val)
37 {
38 r->next=p;
39 p=p->next;
40 }
41 else
42 {
43 r->next=q;
44 q=q->next;
45 }
46 r=r->next;
47 }
48
49 while(p!=NULL)
50 {
51 r->next=p;
52 r=r->next;
53 p=p->next;
54 }
55
56 while(q!=NULL)
57 {
58 r->next=q;
59 r=r->next;
60 q=q->next;
61 }
62
63 r=NULL;
64
65 return First;
66 }
67 };
p1 p2 指向开头,p1的每次移动步长为1,p2的每次移动的步长为2。在p2==NULL前,如果出现p1==p2,则有环。
1 #include <stdio.h>
2 #include<stdlib.h>
3 struct Node
4 {
5 int val;
6 Node * next;
7 };
8
9 Node* Node_Create(Node* p,int val)
10 {
11 p=(Node*)calloc(1,sizeof(Node));
12 p->val=val;
13 p->next=NULL;
14 return p;
15 }
16
17 int If_Have_Circle(Node* First)
18 {
19 if( First==NULL) return 0;
20 Node* p1=First;
21 Node* p2=First;
22 int Have=0;
23 while(p1!=NULL&&p2!=NULL)
24 {
25 p1=p1->next;
26 if(p1==NULL) break;
27
28 p2=p2->next;
29 if(p2==NULL) break;
30 p2=p2->next;
31 if(p2==NULL) break;
32
33 if(p1==p2)
34 {
35 Have=1;
36 break;
37 }
38 }
39
40 return Have;
41 }
42 int main()
43 {
44 int i,tem;
45
46 Node* No_Circle_First=NULL;
47 Node* Have_Circle_First=NULL;
48
49 Node* p=NULL;
50 Node* q=NULL;
51 q=Node_Create(q,1);
52 p=q;
53 No_Circle_First=q;
54
55 q=Node_Create(q,2);
56 p->next=q;
57 p=p->next;
58 q=Node_Create(q,3);
59 p->next=q;
60 p=p->next;
61 q=Node_Create(q,4);
62 p->next=q;
63
64 q=Node_Create(q,1);
65 p=q;
66 Have_Circle_First=q;
67
68 q=Node_Create(q,2);
69 p->next=q;
70 p=p->next;
71
72 q=Node_Create(q,3);
73 p->next=q;
74 p=p->next;
75 Node* index=p;
76
77 q=Node_Create(q,4);
78 p->next=q;
79 p=p->next;
80
81 q=Node_Create(q,5);
82 p->next=q;
83 p=p->next;
84 p->next=index;
85
86 int tem1=If_Have_Circle(No_Circle_First);
87 printf("%s\n",tem1==0?"No":"Yes");
88 tem1=If_Have_Circle(Have_Circle_First);
89 printf("%s\n",tem1==0?"No":"Yes");
90 return 0;
91 }
先计算出两条链表的长度L1、L2,n=ans(L1-L2)。p1,p2分别指向两个链表的开头,指向长的链表的指针先向前移动n次,然后再两个一起移动。如果出现p1==p2,则开始计数。
1 #include <stdio.h>
2 #include<stdlib.h>
3 struct Node
4 {
5 int val;
6 Node * next;
7 };
8
9 Node* Node_Create(Node* p,int val)
10 {
11 p=(Node*)calloc(1,sizeof(Node));
12 p->val=val;
13 p->next=NULL;
14 return p;
15 }
16
17
18 void Find_Same(Node* First1,Node* First2)
19 {
20 int len1,len2,count;
21 len1=len2=count=0;
22 Node* p,*q;
23 p=First1;
24 while(p!=NULL)
25 {
26 ++len1;
27 p=p->next;
28 }
29
30 p=First2;
31 while(p!=NULL)
32 {
33 ++len2;
34 p=p->next;
35 }
36 p=First1;q=First2;
37 while(len1!=len2)
38 {
39 if(len1>len2)
40 {
41 p=p->next;
42 ++len2;
43 }
44 else
45 {
46 q=q->next;
47 ++len1;
48 }
49 }
50
51 while(p!=q)
52 {
53 p=p->next;
54 q=q->next;
55 }
56
57 while(p!=NULL)
58 {
59 ++count;
60 printf("%d ",p->val);
61 p=p->next;
62 }
63 printf("\n共%d个公共节点\n",count);
64 }
65
66 int main()
67 {
68 int i;
69
70 Node* First1=NULL;
71 Node* First2=NULL;
72
73 Node* p=NULL;
74 Node* q=NULL;
75 q=Node_Create(q,1);
76 p=q;
77 First1=q;
78
79 q=Node_Create(q,2);
80 p->next=q;
81 p=p->next;
82 q=Node_Create(q,3);
83 p->next=q;
84 p=p->next;
85 Node* index=p;
86 q=Node_Create(q,4);
87 p->next=q;
88
89 q=Node_Create(q,1);
90 p=q;
91 First2=q;
92 p->next=index;
93 Find_Same(First1,First2);
94 return 0;
95 }
链表只能相邻改变,所以用冒泡排序最好。
1 #include <stdio.h>
2 #include<stdlib.h>
3 struct Node
4 {
5 int val;
6 Node * next;
7 };
8
9 Node* Node_Insert(Node* First,int val)
10 {
11 Node* p=(Node*)calloc(1,sizeof(Node));
12 p->val=val;
13 p->next=First;
14 First=p;
15 return First;
16 }
17
18 void order(Node* First)
19 {
20 Node* p=First;
21 while(p!=NULL)
22 {
23 printf("%d ",p->val);
24 p=p->next;
25 }
26 }
27
28
29 Node* Node_sort(Node* First)
30 {
31 if(First==NULL)
32 return First;
33 Node* p1,*p2,*pre;
34 Node* rear=First;
35 Node* L=(Node*)calloc(1,sizeof(Node));
36 L->next=First;
37 while(rear->next!=NULL)
38 rear=rear->next;
39 while(rear!=First)
40 {
41 pre=L;
42 p1=L->next;
43 p2=L->next->next;
44 while(p2!=rear->next&&p2!=NULL)
45 {
46 if(p1->val>p2->val)
47 {
48 pre->next=p1->next;
49 p1->next=p2->next;
50 p2->next=p1;
51 pre=pre->next;
52 p2=p1->next;
53 }
54 else
55 {
56 pre=pre->next;
57 p1=p1->next;
58 p2=p2->next;
59 }
60 }
61
62 rear=pre;
63 }
64
65 return L->next;
66 }
67
68 int main()
69 {
70 int n,i,tem;
71 while(printf("链表长度:")&&scanf("%d",&n)!=EOF)
72 {
73 getchar();
74 Node* First=NULL;
75 printf("请插入链表:");
76 for(i=0;i<n;i++)
77 {
78 scanf("%d",&tem);
79 First=Node_Insert(First,tem);
80 }
81 getchar();
82 printf("链表为:");
83 order(First);
84 printf("\n");
85
86 First=Node_sort(First);
87 printf("排序后为:");
88 order(First);
89 printf("\n");
90 }
91 return 0;
92 }
用Hash数组保存各相同元素值的个数
1 #include <stdio.h>
2 #include<stdlib.h>
3
4 struct Node
5 {
6 int val;
7 Node * next;
8 };
9
10 Node* Node_Insert(Node* First,int val)
11 {
12 Node* p=(Node*)calloc(1,sizeof(Node));
13 p->val=val;
14 p->next=First;
15 First=p;
16 return First;
17 }
18
19 void order(Node* First)
20 {
21 Node* p=First;
22 while(p!=NULL)
23 {
24 printf("%d ",p->val);
25 p=p->next;
26 }
27 }
28
29 int cnt[101];
30
31 Node* Delete_Same(Node* First)
32 {
33 Node* p=First;
34 Node* pre,*r;
35 while(p!=NULL)
36 {
37 ++cnt[p->val];
38 p=p->next;
39 }
40 Node* L=(Node*)calloc(1,sizeof(Node));
41 L->next=First;
42 pre=L;
43 p=First;
44 while(p!=NULL)
45 {
46 if(cnt[p->val]>1)
47 {
48 --cnt[p->val];
49 r=p;
50 p=p->next;
51 pre->next=p;
52 free(r);
53 }
54 else
55 {
56 p=p->next;
57 pre=pre->next;
58 }
59 }
60
61 return L->next;
62 }
63
64 int main()
65 {
66 int n,i,tem,tem2;
67 while(printf("链表长度:")&&scanf("%d",&n)!=EOF)
68 {
69 getchar();
70 Node* First=NULL;
71 printf("请插入链表:");
72 for(i=0;i<n;i++)
73 {
74 scanf("%d",&tem);
75 First=Node_Insert(First,tem);
76 }
77 printf("原链表:");
78 order(First);
79 printf("\n");
80
81 for(i=0;i<101;i++)
82 cnt[i]=0;
83 First=Delete_Same(First);
84
85 printf("删除后:");
86 order(First);
87 printf("\n");
88
89 }
90 return 0;
91 }
1 #include <stdio.h>
2 #include<stdlib.h>
3 struct Node
4 {
5 int val;
6 Node * next;
7 };
8
9 Node* Node_Insert(Node* First,int val)
10 {
11 Node* p=(Node*)calloc(1,sizeof(Node));
12 p->val=val;
13 p->next=First;
14 First=p;
15 return First;
16 }
17
18
19 void order(Node* First)
20 {
21 Node* p=First;
22 while(p!=NULL)
23 {
24 printf("%d ",p->val);
25 p=p->next;
26 }
27 }
28
29 void Node_Cut(Node* First,Node* &First1,Node* &First2)
30 {
31 if(First==NULL)
32 return;
33 if(First->next==NULL)
34 {
35 First1=First;
36 First1->next=NULL;
37 return;
38 }
39
40 First1=First;
41 First2=First->next;
42
43 Node* p1=First1;
44 Node* p2=First2;
45 while(p1!=NULL&&p2!=NULL)
46 {
47 if(p1->next==NULL) break;
48 if(p1->next->next==NULL) break;
49 p1->next=p1->next->next;
50 p1=p1->next;
51
52 if(p2->next==NULL) break;
53 if(p2->next->next==NULL) break;
54 p2->next=p2->next->next;
55 p2=p2->next;
56 }
57 p1->next=NULL;
58 p2->next=NULL;
59 }
60
61 int main()
62 {
63 int n,i,tem,tem2;
64 while(printf("链表长度:")&&scanf("%d",&n)!=EOF)
65 {
66 getchar();
67 Node* First=NULL;
68 Node* First1=NULL;
69 Node* First2=NULL;
70 printf("请插入链表:");
71 for(i=0;i<n;i++)
72 {
73 scanf("%d",&tem);
74 First=Node_Insert(First,tem);
75 }
76 printf("原链表:");
77 order(First);
78 printf("\n");
79
80 Node_Cut(First,First1,First2);
81 printf("拆分后:\n");
82 order(First1);
83 printf("\n");
84 order(First2);
85 printf("\n");
86
87 }
88 return 0;
89 }
1 #include<stdio.h>
2 #include<stdlib.h>
3
4 struct Node
5 {
6 int val;
7 Node * next;
8 };
9
10 Node* Node_Insert(Node* First,int val)
11 {
12 Node* p=(Node*)calloc(1,sizeof(Node));
13 p->val=val;
14 p->next=First;
15 First=p;
16 return First;
17 }
18
19
20 void order(Node* First)
21 {
22 Node* p=First;
23 while(p!=NULL)
24 {
25 printf("%d",p->val);
26 p=p->next;
27 }
28 }
29
30 int jinwei,tuiwei;
31
32 Node* add1(Node* Long_Num,Node* Short_Num)// 同号整数相加
33 {
34 Node* p1,*p2;
35 p1=Long_Num;p2=Short_Num;
36 while(p2!=NULL)
37 {
38 p1->val+=p2->val;
39 p1=p1->next;
40 p2=p2->next;
41 }
42
43 Node* p3=Long_Num;
44 while(p3!=p1)
45 {
46 if(p3->val>=10)
47 {
48 if(p3->next==NULL)
49 {
50 jinwei=1;//进位
51 p3->val=p3->val%10;
52 }
53 else
54 {
55 p3->next->val+=p3->val/10;
56 p3->val=p3->val%10;
57 }
58 }
59 p3=p3->next;
60 }
61
62 return Long_Num;
63 }
64
65 Node* add2(Node* Long_Num,Node* Short_Num)//异号相加
66 {
67 Node* p1,*p2;
68 p1=Long_Num;p2=Short_Num;
69 while(p2!=NULL)
70 {
71 p1->val-=p2->val;
72 p1=p1->next;
73 p2=p2->next;
74 }
75 Node* p3=Long_Num;
76 while(p3!=p1)
77 {
78 if(p3->val<0)
79 {
80
81 --p3->next->val;
82 p3->val+=10;
83 }
84 p3=p3->next;
85 }
86 return Long_Num;
87 }
88
89 int My_Compare(Node* Num1,Node* Num2)
90 {
91 Node* p1,*p2;
92 p1=Num1;
93 p2=Num2;
94 while(p1!=NULL)
95 {
96 if(p1->val>p2->val) return 1;
97 if(p1->val<p2->val) return -1;
98 p1=p1->next;
99 p2=p2->next;
100 }
101 return 0;
102 }
103
104 Node* Chain_Reverse(Node* First)
105 {
106 if(First!=NULL)
107 {
108 Node * pre=NULL;
109 Node * p=First;
110 Node * q=First->next;
111 while(q!=NULL)
112 {
113 p->next=pre;
114 pre=p;
115 p=q;
116 q=q->next;
117 }
118 p->next=pre;
119 return p;
120 }
121 return First;
122
123 }
124
125 int main()
126 {
127 printf("输入格式为:\nNum1\n+\nNum2\n");
128 while(1)
129 {
130 Node* Num1,* Num2;
131 Num1=NULL;
132 Num2=NULL;
133 char tem;
134 int fir=1;
135 int fu1,fu2;
136 int len1,len2;
137 char Highest_Val1,Highest_Val2;
138 len1=len2=0;
139 while(scanf("%c",&tem))//第一个数
140 {
141 if(tem=='\n') break;
142 if(fir)
143 {
144 fir=0;
145 if(tem=='-')
146 {
147 fu1=1;
148 scanf("%c",&Highest_Val1);
149 Num1=Node_Insert(Num1,Highest_Val1-'0');
150 ++len1;
151 }
152 else
153 {
154 fu1=0;
155 ++len1;
156 Highest_Val1=tem;
157 Num1=Node_Insert(Num1,tem-'0');
158 }
159
160 }
161 else
162 { ++len1;
163 Num1=Node_Insert(Num1,tem-'0');
164 }
165
166 }
167 getchar();
168 getchar();
169
170 fir=1;
171 while(scanf("%c",&tem))//第二个数
172 {
173 if(tem=='\n') break;
174 if(fir)
175 {
176 fir=0;
177 if(tem=='-')
178 {
179 fu2=1;
180 scanf("%c",&Highest_Val2);
181 Num2=Node_Insert(Num2,Highest_Val2-'0');
182 ++len2;
183 }
184 else
185 {
186 fu2=0;
187 ++len2;
188 Highest_Val2=tem;
189 Num2=Node_Insert(Num2,tem-'0');
190 }
191 }
192 else
193 {
194 ++len2;
195 Num2=Node_Insert(Num2,tem-'0');
196 }
197 }
198 Node* result;
199 jinwei=tuiwei=0;
200 if(fu1==0&&fu2==0) //全正
201 {
202 if(len1>len2) result=add1(Num1,Num2);
203 else result=add1(Num2,Num1);
204 result=Chain_Reverse(result);
205 if(jinwei) printf("1");
206 order(result);
207 printf("\n");
208 }
209 else if(fu1==1&&fu2==1) //全负
210 {
211 if(len1>len2) result=add1(Num1,Num2);
212 else result=add1(Num2,Num1);
213 result=Chain_Reverse(result);
214 printf("-");
215 if(jinwei) printf("1");
216 order(result);
217 printf("\n");
218 }
219 else if((fu1==1&&fu2==0)||(fu1==0&&fu2==1)) //正负相加
220 {
221 int bigger=1;
222 int cmp=100;
223 if(len1>len2) result=add2(Num1,Num2);
224 else if(len1<len2)
225 {
226 bigger=2;
227 result=add2(Num2,Num1);
228 }
229 else if(len1==len2)
230 {
231 Num1=Chain_Reverse(Num1);
232 Num2=Chain_Reverse(Num2);
233 cmp=My_Compare(Num1,Num2);
234 Num1=Chain_Reverse(Num1);
235 Num2=Chain_Reverse(Num2);
236 if(cmp==1) result=add2(Num1,Num2);
237 else if(cmp==-1)
238 {
239 bigger=2;
240 result=add2(Num2,Num1);
241 }
242 }
243
244 if(cmp==0) printf("0\n");
245 else
246 {
247 result=Chain_Reverse(result);
248 Node* p=result;
249 while(p->val==0)
250 p=p->next;
251 if(bigger==1)
252 {
253 if(fu1) printf("-");
254 }
255 else if(bigger==2)
256 {
257 if(fu2) printf("-");
258 }
259 while(p!=NULL)
260 {
261 printf("%d",p->val);
262 p=p->next;
263 }
264 printf("\n");
265 }
266 }
267
268 }
269 return 0;
270 }