链表操作算法题合集

阅读量：4290 次

发布时间：2019-05-27

本文共 18236 字，大约阅读时间需要 60 分钟。

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

0.单链表的增、删、改、查（无头指针）

1 #include 
     
        2 #include
      
         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

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

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

*p,*q 指向第一个指针，p向前移动n次，q再跟着和p一直移动，等p移到末尾，q所指的就是倒是第n个元素

1 #include 
      
        2 #include
       
         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
        
         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

3.找出单链表的中间元素（见0）

4.删除无头单链表的一个节点（见0）

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: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
     
      val)23         {24             r=p;25             p=p->next;26         }27         else28         {29             r=q;30             q=q->next;31         }32 33     First=r;34     while(p!=NULL&&q!=NULL)35     {36         if(p->val
      
       val)37         {38             r->next=p;39             p=p->next;40         }41         else42         {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 
      
        2 #include
       
         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 }

7.判断两个单链表是否相交（见8）

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

先计算出两条链表的长度L1、L2，n=ans(L1-L2)。p1,p2分别指向两个链表的开头，指向长的链表的指针先向前移动n次，然后再两个一起移动。如果出现p1==p2，则开始计数。

1 #include 
      
        2 #include
       
         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         else45         {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 
      
        2 #include
       
         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             else55             {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

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

用Hash数组保存各相同元素值的个数

1 #include 
      
        2 #include
       
         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         else55         {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

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

1 #include 
      
        2 #include
       
         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

12 大整数加法

1 #include
      
         2 #include
       
          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
        
         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                 else153                 {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                 else185                 {186                     fu2=0;187                     ++len2;188                     Highest_Val2=tem;189                     Num2=Node_Insert(Num2,tem-'0');190                 }191             }192             else193             {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
         
          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 }