必备知识架构-数据结构

[toc]

一、单链表

我们都知道单链表中结点都是一个结点指向下一个结点这样一个一个链接起来的，直到尾结点的指针域没有指向，单链表就到此结束了。

题目：已知下列是一个有环的单链表，请问如何判断单链表是否存在环

有环的单链表

分析：把环想象成操作。

则我们通过使用快慢指针判断单链表是否存在环。
使用slow、fast 2个指针，slow慢指针每次向前走1步，fast快指针每次向前走2步，
若存在环的话，必定存在某个时候 slow = fast 快慢指针相遇。
list 带头结点的单链表
返回值 >0:存在环返回环的位置 0:不存在环

在相遇点，由于两个指针继续一个走一步，一个走两步，当再次相遇时，走一步的指针所走过的节点数记为环/操场的长度。

\那么问题来了，既然知道该单链表是代码单链表，那么我怎样将其还原为正常单链表呢？**

我们只需要将尾结点的next指针域置为NULL就还原为正常单链表了。我们怎样找到尾结点呢？请看代码。