快慢指针和其简单应用

bool isLoop(LinkList L) {LinkList fast, slow;fast &＃61; slow &＃61; L;while (fast && fast->next){slow &＃61; slow->next;fast &＃61; fast->next->next;if (slow &＃61;&＃61; fast){return true; }}return false;
}


例如长度为8&＃xff0c;从1开始&＃xff1a;

while(fast&&slow)
{if(fast->next&＃61;&＃61;NULL)return slow->date;if(fast->next!&＃61;NULL&&fast->next->next&＃61;&＃61;NULL)return (slow->date&＃43;slow->next->date)/2;fast&＃61;fast->next->next;slow&＃61;slow->next;
}

3.如果链表存在环&＃xff0c;怎么找到环的入口点呢&＃xff1f;

       有一个单链表&＃xff0c;其中可能有一个环&＃xff0c;也就是某个节点的next指向的是链表中在它之前的节点&＃xff0c;这样在链表的尾部形成环。
       那么问题来了&＃xff0c;如何判断一个链表是这类链表呢&＃xff1f;即如果链表存在环&＃xff0c;怎么找到入口点呢&＃xff1f;
      ① 如果循环方式为上图所示&＃xff0c;即尾部有循环&＃xff0c;当fast&＃xff08;两倍速&＃xff09;与slow相遇时&＃xff0c;slow一定没有走完链表。
      ②如果循环入口点为头结点&＃xff0c;如上面表格情况&＃xff0c;那么slow恰好遍历一圈。
       对于第一种情况&＃xff08;如上图&＃xff09;&＃xff0c;我们从链表头A点与相遇点P点分别设置一个指针&＃xff0c;每次各走一步&＃xff0c;两个指针必定相遇&＃xff08;一定存在循环啦&＃xff09;&＃xff0c;且第一次相遇点就是环的入口了。
       解释&＃xff1a;A点为出发点&＃xff0c;fast和slow在p点相遇&＃xff0c;所以A->B->P 步数等于P->B->P  所以A->B等于P->B 那么如果在A点和p点分别设置一个指针&＃xff0c;每次各走一步&＃xff0c;两个指针就会在B点相遇&＃xff0c;即相遇在环的入口处。
        对于第二种情况&＃xff0c;相遇点即链表头&＃xff0c;也就是环的入口了。

代码示例&＃xff1a;