# 链表操作算法题合集

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.单链表反转

```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) {
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 };```

# 2.找出单链表的倒数第n个元素

*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 }```

# 5.两个不交叉的有序链表的合并

```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:
12     {
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 };```

# 6.判断单链表是否有环？

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 }```

# 8.两个单链表相交，计算相交点

```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 }```

# 9.单链表排序

```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 }```

# 10.删除单链表中重复的元素

```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 }```

# 11 链表拆分(将链表奇数位置上的节点构成一个新链表，偶数位置上的结点构成一个新链表)

```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 }```

# 12 大整数加法

```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         {
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         {
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;
224             else if(len1<len2)
225             {
226                 bigger=2;
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);
237                 else if(cmp==-1)
238                 {
239                     bigger=2;
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 }```

0 条评论

• ### 《深度学习Ng》课程学习笔记04week1——卷积神经网络

http://blog.csdn.net/u011239443/article/details/79057016 1.1 计算机视觉 计算机视觉领域的问题 图片...

• ### 《机器学习技法》学习笔记03——核SVM

http://blog.csdn.net/u011239443/article/details/76598872

• ### 《机器学习实战（Scala实现）》（二）——k-邻近算法

1.计算中的set中每一个点与Xt的距离。 2.按距离增序排。 3.选择距离最小的前k个点。 4.确定前k个点所在的label的出现频率。 5....

• ### LeetCode 1490. 克隆 N 叉树（DFS/BFS）

N 叉树的每个节点都包含一个值（ int ）和子节点的列表（ List[Node] ）。

• ### .net core安装及初体验

.net core 作为微软的新一代技术，在开发跨平台、微服务等方面有很大的优势，也更贴近现代的编码习惯。在2.0版发布很久以后，近期终于决定进行学习和体验。

• ### 今天你为什么更应该学习JavaScript？

几周前的NodeSummit 2016结束后，给人感觉是毫无疑问Javascript和特别是Node正在蚕食世界。 NodeSummit提供几个案例学习显示，...

• ### 前端有必要去学Node.js吗？

Node近两年已经成为前端知识栈必备技能之一。随便点开招聘网站找个岗位几乎都会要求会Node，更不用提一些高级岗位了。

• ### Mantel correlogram

随便找了个OTU，计算weighted和unweighted Unifrac距离矩阵和环境因子距离矩阵，分别用vegan的mantel.correlog和eco...

• ### JavaScript点击表格的表头，实现表格排序

1）页面预设布局 页面上事先给出表头，具体html代码如下： 其中表头的key属性作用后面说明。