概述
单向链表
链表中最简单的一种是单向链表，它包含两个域，一个信息域和一个指针域。这个链接指向列表中的下一个节点，而最后一个节点则指向一个空值。
一个单向链表的节点被分成两个部分。第一个部分保存或者显示关于节点的信息，第二个部分存储下一个节点的地址。单向链表只可向一个方向遍历。
循环链表
在一个 循环链表中, 首节点和末节点被连接在一起。这种方式在单向和双向链表中皆可实现。要转换一个循环链表，你开始于任意一个节点然后沿着列表的任一方向直到返回开始的节点。再来看另一种方法，循环链表可以被视为“无头无尾”。这种列表很利于节约数据存储缓存， 假定你在一个列表中有一个对象并且希望所有其他对象迭代在一个非特殊的排列下。
指向整个列表的指针可以被称作访问指针。
循环链表中第一个节点之前就是最后一个节点，反之亦然。循环链表的无边界使得在这样的链表上设计算法会比普通链表更加容易。对于新加入的节点应该是在第一个节点之前还是最后一个节点之后可以根据实际要求灵活处理，区别不大(详见下面实例代码)。当然，如果只会在最后插入数据（或者只会在之前），处理也是很容易的。
应用
判断链表是否有环
网上关于判断链表是否有环，一般都是指的是单链表，并未特指循环链表，因为循环链表没有头节点，本身确实有环。所以接下来我们分析的都是以单链表为主，如下图所示，为有环链表。
分析：
以图片为例，假设环的长度为 R，这里使用俩指针 p 和 q，p 扫描的步长为 2, q 扫描的步长为 1。头指针 header 到入口点 entry之间的距离是 K，则当 q 入环的时候， p 和 q 之间的距离为 S。在 q 指针进入环后的 t 时间内，p 指针从距离环入口 S 处走了 2t 个节点，相当于从环入口走了 S+2t 个节点。而此时 p 指针从环入口走了 t 个节点。
假设两个节点相遇，则说明链表有环。那么一定存在公式为 S+2t - t = nR，即 S+t=nR。其中 n 大于 0，由于 S<R，所以在 q 指针走过一圈之前就可以相遇。
所以如果链表中有环，那么当 q 指针进入到环时，在未来的某一时刻，p 和 q 指针一定可以相遇，通过这个也就可以判断链表是否有环。
代码实现：
import string
#节点对象
class Node():
def __init__(self, val=None):
self.val = val #节点数据值
self.next = None #相连的下一个节点对象
def __str__(self):
return str(self.val)
#单链表
class SingleLinkList():
def __init__(self, node=None):
self._header = node
def add(self, var):
'''
单链表添加元素
:param var:传过来的数据
:return:
'''
node = Node(var) # 将数据封装为节点
if self._header == None:
self._header = node
else:
cur = self._header
while cur.next != None:
cur = cur.next #移动游标
cur.next = node
def traversal(self):
'''
遍历输出单链表
:return:
'''
if self._header == None:
return
else:
cur = self._header
while cur != None:
print(cur,end=' ')
cur = cur.next
print()
def fprint_cycle(self, length):
'''
输出有环链表，因为有环，所以如果按照之前的输出方法，会一直输出，所以我们只输出到交叉点
:param length: 无环链表的长度加 1
:return:
'''
cur = self._header
for i in range(length):
print(cur, end=' ')
cur = cur.next
print()
def size(self):
'''
链表长度
:return:
'''
count = 0
if self._header != None:
cur = self._header
while cur != None:
count += 1
cur = cur.next
return count
def setCycleList(self, index):
'''
输入索引值，确定哪一点为交叉点，即环入口点
:param index:
:return:
'''
size = self.size()
if size == 0:
print('Empty,can\'t delete')
return
if index <= 0 or index > size-1:
print('Index is error')
return
cur = self._header
while cur.next != None:
cur = cur.next
tail_node = cur #获取尾节点
cur = self._header
pre = cur
for i in range(index + 1): #获取链表环的交叉点
pre = cur
cur = cur.next
tail_node.next = pre #尾节点指向交叉点，组成一个环
def hasCycle(self):
'''
判断单链表是否有环
:return:有环返回True，否则为 False
'''
p = self._header
q = self._header
while p != None and p.next != None:#当p快指针和q慢指针相遇，则说明存在环
p = p.next.next
q = q.next
if p == q: #此时p指针和q指针同时指向同一个节点
return True
return False
if __name__ == '__main__':
single_link = SingleLinkList()
for i,v in enumerate(string.ascii_lowercase):
if i == 12:
break
single_link.add(v)
print("对链表进行遍历")
single_link.traversal()
size = single_link.size()
#构建有环链表
single_link.setCycleList(4)
single_link.fprint_cycle(size+1)
#判断链表是否有环
if single_link.hasCycle():
print('该链表有环！')
计算链表中环的长度
如上述分析一致，当 p 指针和 q 指针第一次相遇时，p 指针走过的路程比 q 指针多出的距离即为环长 R，因此可得以下代码：
def getCycle_length(self):
'''
计算链表中环的长度
:return:
'''
p = self._header
q = self._header
p_distance = 0
q_distance = 0
R = 0
while p != None and p.next != None: # 当p快指针和q慢指针相遇，则说明存在环
p = p.next.next
p_distance += 2
q = q.next
q_distance += 1
if p == q:
R = p_distance - q_distance
break
return R
计算链表的入环点
分析：
根据 p 和 q 指针首次相遇画出如下抽象示意图。
假设从链表头节点到入环点的距离是 D，从入环点到两个指针首次相遇点的距离是 S1，从首次相遇点回到入环点的距离是 S2。
p 指针和 q 指针首次相遇时，各自走的距离为：L(q) = D+S1，L(p) = D+S1+S2+S1。
由于 p 指针的速度是 q 的 2 倍，所以所走的距离也是 q 的 2 倍，因此：2(D+S1) = D+2S1+S2，即为：D = S2。
从公式可以看出，从链表头节点到入环点的距离，等于从首次相遇点回到入环点的距离。因此我们重新选择两个速度一致的节点，一个从头节点位置出发，另一个从首次相遇点出发，那么，它们最终相遇的节点，就是入环点。
代码实现：
def get_intersection(self):
p = self._header
q = self._header
r = self._header
s = None
while p != None and p.next != None: # 当p快指针和q慢指针相遇，则说明存在环
p = p.next.next
q = q.next
if p == q: # 此时p指针和q指针同时指向同一个节点
s = p
break
while r != s:
r = r.next
s = s.next
e = r
return e
本文作者为hresh，转载请注明。