<链表>续一

1、单链表逆置

View Code

 1 //1.单链表逆置
 2 template<class Type> void LinkList<Type>::Reverse()
 3 {
 4     if(Head->Next==NULL)
 5     {
 6         cout<<"链表为空!"<<endl;
 7         return;
 8     }
 9     Node *cur=Head->Next;
10     Node *temp=cur->Next;
11     if(NULL==cur || NULL==temp)
12     {
13         return;
14     }
15     Head->Next=NULL;
16     while(cur!=NULL)
17     {
18         cur->Next=Head->Next;
19         Head->Next=cur;
20         cur=temp;
21         if(temp!=NULL)
22             temp=temp->Next;
23     }
24 }

2、找到链表倒数第n个元素

View Code

 1 //找到链表倒数第n个元素
 2 template<class Type> Type LinkList<Type>::FindLastOf(int n)
 3 {                            
 4     Node *cur=Head->Next;
 5     Node *temp=Head;
 6     while(cur!=NULL)
 7     {
 8         if(--n>0)
 9         {
10             cur=cur->Next;
11             if(cur==NULL)//不利用链表中的size属性,考虑输入数字大于链表长度
12             {
13                 cout<<"数字大于链表长度!"<<endl;
14                 exit(0);
15             }
16         }
17         else
18         {
19             temp=temp->Next;
20             cur=cur->Next;
21         }    
22     }
23     return temp->data;
24 }

3、打印出链表的中间元素

View Code

 1 //3.打印出链表的中间元素
 2 template<class Type> void LinkList<Type>::PrintMiddleData()
 3 {                                    //打印出链表的中间元素(考虑链表的长度为奇数和偶数的情况)
 4     Node *first,*second;            //使用两个指针first和second，first一次走两步，second每次走一步
 5     first=second=Head;
 6     while(first!=NULL&&first->Next!=NULL)
 7     {
 8         first=first->Next->Next;
 9         second=second->Next;
10     }
11     if(first==NULL)//元素个数为奇数
12     {
13         cout<<second->data<<endl;
14     }
15     else//元素个数为偶数
16     {
17         if(second!=Head)
18         {
19             cout<<second->data<<" "<<second->Next->data<<endl;
20         }
21     }
22 }