链表操作

  1 #include<stdio.h>
  2 #include<stdlib.h>
  3 
  4 typedef struct node
  5 {
  6     int data;
  7     node* next;
  8 } Node;
  9 
 10 Node* head = null;
 11 
 12 //创建链表
 13 bool createNodeList()
 14 {
 15     head = (Node*)malloc(sizeof(Node));
 16     if(null == head)
 17         return false;
 18     else
 19     {
 20         head->data=0;
 21         head->next=null;
 22         return true;        
 23     }    
 24 }
 25 
 26 //销毁链表
 27 void destroyNodeList()
 28 {
 29     if(null==head)
 30         return;
 31     if(null==head->next)
 32     {
 33         free(head);
 34         head==null;
 35         return;
 36     }
 37     Node* p=head->next;
 38     while(null!=p)
 39     {
 40         Node* tmp=p;
 41         p=p->next;
 42         free(tmp);
 43     }
 44     free(head);
 45     head=null;
 46 }
 47 
 48 //删除节点
 49 bool delNode(int index)
 50 {
 51     if(null == head)
 52         return false;
 53     Node* p = head->next();
 54     int length = 0;
 55     while(null!=p)
 56     {
 57         length++;
 58         p=p->next;
 59     }
 60     if(length<index)
 61         return false;
 62     else
 63     {
 64         Node* q = head;
 65         p=head;
 66         for(int i=0;i<index;i++)
 67         {
 68             q=p;
 69             p=p->next;        
 70         }
 71         Node* t=p->next;
 72         q->next=t;
 73         free(p);
 74     }
 75 }
 76 
 77 //链表逆序
 78 void reverseNodeList()
 79 {
 80     if(null == head)
 81         return;
 82     if(null == head->next)
 83         return;
 84         
 85     Node* p=head->next;
 86     Node* q=p->next;
 87     Node* t=null;
 88     while(q!=null)
 89     {
 90         t=q->next;
 91         q->next=p;
 92         p=q;
 93         q=t;
 94     }
 95     head->next->next=null;
 96     head->next=p;
 97 }
 98 
 99 //降序排序-冒泡排序
100 void sortDesc()
101 {
102     if(null == head)
103         return;
104     if(null == head->next)
105         return;
106         
107     Node* pi=head->next;
108     Node* pj=pi->next;
109     for(;pi!=null;pi=pi->next)
110     {
111         for(pj=pi->next;pj!=null;pj=pj->next)
112         {
113             if(pj->data>pi->data)
114             {
115                 int tmp=pj->data;
116                 pj->data=pi->data;
117                 pi->data=tmp;    
118             }    
119         }    
120     }
121 }
122 
123 //合并有序的两个链表
124 Node* merge(Node* head1,Node* head2)
125 {
126     if(null==head1)
127         return head2;
128     if(null==head2)
129         return head1;
130         
131     Node* head=null;
132     Node* p1=null;
133     Node* p2=null;
134     if(head1->data < head2->data)
135     {
136         head=head1;
137         p1=head1->next;
138         p2=head2;
139     }
140     else
141     {
142         head=head2;
143         p1=head1;
144         p2=head2->next;
145     }
146     Node* pCurr=head;
147     while(p1!=null&&p2!=null)
148     {
149         if(p1->data<p2->data)
150         {
151             pCurr->next=p1;
152             pCurr=p1;
153             p1=p1->next;
154         }
155         else
156         {
157             pCurr->next=p2;
158             pCurr=p2;
159             p2=P2->next;
160         }
161     }
162     if(null!=p1)
163         pCurr->next=p1;
164     if(null!=P2)
165         pCurr->next=p2;
166     return head;
167 }
168 
169 //合并有序的两个链表-递归
170 Node* merge(Node* head1,Node* head2)
171 {
172     if(null==head1)
173         return head2;
174     if(null==head2)
175         return head1;
176         
177     Node* head=null;
178     if(head1->data<head2->data)
179     {
180         head=head1;
181         head->next=merge(head1->next,head2);
182     }
183     else
184     {
185         head=head2;
186         head->next=merge(head1,head2->next);
187     }
188     return head;
189 }
190 
191 //判断单链表是否有环
192 bool check(const Node* head)
193 {
194     if(null==head)
195         return false;
196     Node* low=head;
197     Node* fast=head->next;
198     while(fast->next!=null)
199     {
200         low=low->next;
201         fast=fast->next->next;
202         if(low==fast)
203             return true;
204     }
205     return false;
206 }