文章目录[隐藏]
Description
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
Thought
双指针技巧,当快慢指针相遇时，其中一个再去头节点，此时快慢指针同步运行（1个step），再次相遇时就为我们需要的节点。不要被题干中的pos给引导了
Solution
- Accepted
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def detectCycle(self, head: ListNode) -> ListNode:
fast = head
slow = head
while(fast != None and slow !=None):
# 无环的情况
if(fast.next == None):
return None
fast = fast.next.next
slow = slow.next
if(fast == slow):
slow = head
while(fast != slow):
slow = slow.next
fast = fast.next
return slow
break
- Time Limit Exceeded，有点疑惑为啥单独搞一个ListNode就不行呢？
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(head.__len__()):
listN.next = ListNode(head[m])
listN = listN.next
# 有环状的情况
# 这中忽略了pos为0的情况
if m == pos:
cir = listN
if cir.next != None:
listN.next = cir
# solve this problem
get_pos = ListNode(-1)
fast = tmp
slow = tmp
while(fast != None and slow !=None):
# 无环的情况
if(fast.next == None):
get_pos.val = None
return get_pos
fast = fast.next.next
slow = slow.next
if(fast == slow):
slow = tmp
while(fast != slow):
slow = slow.next
fast = fast.next
get_pos.val += 1
return get_pos
break
head = [3,2,0,-4]
S = Solution()
print(S.hasCycle(head).val)
