一步一步写算法（之循环单向链表）

【 声明：版权所有，欢迎转载，请勿用于商业用途。  联系信箱：feixiaoxing @163.com】

    前面的博客中，我们曾经有一篇专门讲到单向链表的内容。那么今天讨论的链表和上次讨论的链表有什么不同呢？重点就在这个"循环"上面。有了循环，意味着我们可以从任何一个链表节点开始工作，可以把root定在任何链表节点上面，可以从任意一个链表节点访问数据，这就是循环的优势。

    那么在实现过程中，循环单向链表有什么不同？

    1）打印链表数据

void print_data(const LINK_NODE* pLinkNode) 

{ 

    LINK_NODE* pIndex = NULL; 

    if(NULL == pLinkNode) 

        return; 

    printf("%d\n", pLinkNode->data); 

    pIndex = pLinkNode->next; 

    while(pLinkNode != pIndex){ 

        printf("%d\n", pIndex->data); 

        pIndex = pIndex ->next; 

    } 

} 

void print_data(const LINK_NODE* pLinkNode)

{

       LINK_NODE* pIndex = NULL;

       if(NULL == pLinkNode)

              return;

       printf("%d\n", pLinkNode->data);

       pIndex = pLinkNode->next;

       while(pLinkNode != pIndex){

              printf("%d\n", pIndex->data);

              pIndex = pIndex ->next;

       }

}    以往，我们发现打印数据的结束都是判断指针是否为NULL，这里因为是循环链表所以发生了变化。原来的条件（NULL != pLinkNode）也修改成了这里的（pLinkNode != pIndex）。同样需要修改的函数还有find函数、count统计函数。

    2）插入数据

STATUS insert_data(LINK_NODE** ppLinkNode, int data) 

{ 

    LINK_NODE* pNode; 

    if(NULL == ppLinkNode) 

        return FALSE; 

    if(NULL == *ppLinkNode){ 

        pNode = create_link_node(data); 

        assert(NULL != pNode); 

        pNode->next = pNode; 

        *ppLinkNode = pNode; 

        return TRUE; 

    } 

    if(NULL != find_data(*ppLinkNode, data)) 

        return FALSE; 

    pNode = create_link_node(data); 

    assert(NULL != pNode); 

    pNode->next = (*ppLinkNode)->next; 

    (*ppLinkNode)->next = pNode; 

    return TRUE; 

} 

STATUS insert_data(LINK_NODE** ppLinkNode, int data)

{

       LINK_NODE* pNode;

       if(NULL == ppLinkNode)

              return FALSE;

       if(NULL == *ppLinkNode){

              pNode = create_link_node(data);

              assert(NULL != pNode);

              pNode->next = pNode;

              *ppLinkNode = pNode;

              return TRUE;

       }

       if(NULL != find_data(*ppLinkNode, data))

              return FALSE;

       pNode = create_link_node(data);

       assert(NULL != pNode);

       pNode->next = (*ppLinkNode)->next;

       (*ppLinkNode)->next = pNode;

       return TRUE;

}这里的insert函数在两个地方发生了变化：

    a）如果原来链表中没有节点，那么链表节点需要自己指向自己

    b）如果链表节点原来存在，那么只需要在当前的链表节点后面添加一个数据，同时修改两个方向的指针即可

    3） 删除数据

STATUS delete_data(LINK_NODE** ppLinkNode, int data) 

{ 

    LINK_NODE* pIndex = NULL; 

    LINK_NODE* prev = NULL; 

    if(NULL == ppLinkNode || NULL == *ppLinkNode) 

        return FALSE; 

    pIndex = find_data(*ppLinkNode, data); 

    if(NULL == pIndex) 

        return FALSE; 

    if(pIndex == *ppLinkNode){ 

        if(pIndex == pIndex->next){ 

            *ppLinkNode = NULL; 

        }else{ 

            prev = pIndex->next; 

            while(pIndex != prev->next) 

                prev = prev->next; 

            prev->next = pIndex->next; 

            *ppLinkNode = pIndex->next; 

        } 

    }else{ 

        prev = pIndex->next; 

        while(pIndex != prev->next) 

            prev = prev->next; 

        prev->next = pIndex->next; 

    } 

    free(pIndex); 

    return TRUE; 

} 

STATUS delete_data(LINK_NODE** ppLinkNode, int data)

{

       LINK_NODE* pIndex = NULL;

       LINK_NODE* prev = NULL;

       if(NULL == ppLinkNode || NULL == *ppLinkNode)

              return FALSE;

       pIndex = find_data(*ppLinkNode, data);

       if(NULL == pIndex)

              return FALSE;

       if(pIndex == *ppLinkNode){

              if(pIndex == pIndex->next){

                     *ppLinkNode = NULL;

              }else{

                     prev = pIndex->next;

                     while(pIndex != prev->next)

                            prev = prev->next;

                     prev->next = pIndex->next;

                     *ppLinkNode = pIndex->next;

              }

       }else{

              prev = pIndex->next;

              while(pIndex != prev->next)

                     prev = prev->next;

              prev->next = pIndex->next;

       }

       free(pIndex);

       return TRUE;

}和添加数据一样，删除数据也要在两个方面做出改变：

    a）如果当前链表节点中只剩下一个数据的时候，删除后需要设置为NULL

    b）删除数据的时候首先需要当前数据的前一个数据，这个时候就可以从当前删除的数据开始进行遍历

    c） 删除的时候需要重点判断删除的数据是不是链表的头结点数据