使用快慢指针判断单链表是否存在环

时间:2021-12-28 05:23:01

让快慢指针从链表头开始遍历,快指针向前移动两个位置,慢指针向前移动一个位置;如果快指针到达NULL,说明链表以NULL为结尾,不是循环链表。如果快指针追上慢指针,则表示出现了循环。

 

 

C语言实现如下:

int find_loop_in_list(list_node *head)

{

        list_node *fastp, *slowp;

        int i = 0;

        slowp = head;

        fastp = head;

        while(fastp)

        {

                for(i = 0; i < LOOP_TEP; i++)

                {

                        fastp = fastp->next;

                        if(fastp == slowp)

                        {

                                return TRUE;

                        }

                        else if(fastp == NULL)

                                return FALSE;

 

                }

                slowp = slowp->next;

        }

 

        return FALSE;

}