重拾算法：从链表开始

实现把单循环链表例置

算法的思考过程：

第一：需要保存临时数据的变量，不然无法完成倒置。

第二：要完成倒置就需要遍列，又需要一个变量

第三：用于得到最后的结果，这个暂时考虑也需要一个变量

单个节点的倒置是本身，1->1

两个节点的倒置1->2,可以参考两个数的交换，这就需要临时变量了 

p=head;  1

q=head->next; 2

s =p ; 1

q->next = s;2->1

p->next =q; 1->2->1

三个节点。。。。。。。

 

 

 

 

//这样得到了头指针
*p=head;

//2。完成遍列的代码 
*q=head->next;
while(q!=head){
   q=q->next;
}

//需要一个变量保存每次倒置的链表
/*
例如：1->2->1
第一次：1
第二次：2->1
第三次：1->2->1
 这样的话，变量需要在遍列体中

*/


*q=head->next;
while(q!=head){
   s=p;    //这样我们先得到了初始的1 之后和第二，就需要把这个框架完善
   q=q->next;
}

 在确定完方向后，得到下面的函数

 

 

///////////////////////////////////////////////////////////////
//	函 数 名 :invert
//	函数功能 :实现把单循环链表例置
//	处理说明 :1-->2->3->1   转成3->2->1->3
//	作者时间 :	linhai
//	返 回 值 :返回倒置后的链表指针
//	参数说明 :*head 链表的头结点
//	修改记录 :
///////////////////////////////////////////////////////////////
LinkList *invert(const LinkList *head){

    //为了实现倒置，引入三个变量
    //*pResult用于倒置 *pNext 用于遍列链表  *pTemp 用于保存每次倒置后的指针
    LinkList *pResult,*pNext,*pTemp;
    pResult = head;       //1
    pNext = head->next; //2

    while(pNext!=head){
        pTemp=pResult;
        //printf("pTemp=pResult=%d\r\n",pTemp->data);
        pResult=pNext;
        //printf("pResult=q=%d\r\n",pResult->data);
        pNext = pNext->next;
        //printf("q->next=%d\r\n",pNext->data);
        pResult->next=pTemp;
        //outList(pTemp);  输出函数
    }
    pNext->next=pResult; //1->3->2->1

    return pResult;

}

 

在写函数过程中，写变量名时，一定要有意义，明白每个变量的作用，不要一个变量多种用途，这样在写的过程中也比较明白。

上传一个附件：linkDemo，本人使用CodeBlocks编写。

以上代码只是为了自己学习使用，所以在写的过程没考虑太多复杂的情况。倒置只是其中的一个问题，下一篇将写：

                                      报数出圈的问题

这也是循环链表具体使用的实例，也是我一次笔试华为的考题。