文章目录[隐藏]
Description
给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ，则返回 true 。 否则，返回 false 。
方法
快慢指针，如fast指针能遇到NULL则无法成环，当fast和slow相遇则说明成环。
CODE
这里最难搞得是理解ListNode的类
- Python
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def hasCycle(self, head: Optional[ListNode]) -> bool:
fast = head
slow = head
while(fast != None and slow != None):
fast = fast.next.next
slow = slow.next
if fast == slow:
return True
return False
- ListNode的理解
遍历主要要在创建前弄一个中间变量tmp(如下)来记录初始ListNode,环状则应该还需要单独记录一个cir(如下)来把最后的一个ListNode.next 指向这个ListNode。
# Definition for singly-linked list.
import time
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class Solution:
def hasCycle(self, head:ListNode):
listN = ListNode(head[0])
tmp = listN
cir = listN
# pos 为-1时则无环
pos = -1
for m in range(1, head.__len__()):
listN.next = ListNode(head[m])
listN = listN.next
# 有环状的情况
if m == pos:
cir = listN
print(listN.val)
print('---------------')
if cir.next != None:
listN.next = cir
fast = tmp
slow = tmp
while(fast != None and slow !=None):
if(fast.next == None):
return False
fast = fast.next.next
slow = slow.next
if(fast == slow):
return True
head = [3,2,0,-4]
S = Solution()
print(S.hasCycle(head))
print("___________________________________________________________________________________")
listN = ListNode(head[0])
# 中间变量，用来记录处理头listNode节点
tmp = listN
print(listN)
print(tmp)
print(listN.val)
print("#############################")
pos = 1
for m in range(1,head.__len__()):
print("m\t" + str(m))
listN.next = ListNode(head[m])
listN = listN.next
# 有环状的情况
# 标记成环的地方
if m == pos:
cir = listN
print(listN.val)
print('---------------')
# 成环
try:
if cir.next != None:
listN.next = cir
print('try')
except Exception as ex:
print("Exception"+ex)
print(tmp)
print(listN)
print("#############################")
# while True:
# print(listN.val)
# if listN.next != None:
# listN = listN.next
# continue
# else:
# print(listN.next)
# 不能直接用ListN
# 因为上面一直在移动
# 建立一个中间的tmp来表示初始list
while tmp.next != None:
print(tmp.val)
print(tmp)
tmp = tmp.next
time.sleep(1)
