文章目录
- 给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。 如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。 https://leetcode-cn.com/problems/linked-list-cycle-ii
- 双指针技巧,当快慢指针相遇时，其中一个再去头节点，此时快慢指针同步运行（1个step），再次相遇时就为我们需要的节点。不要被题干中的pos给引导了
- 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)
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
双指针技巧,当快慢指针相遇时，其中一个再去头节点，此时快慢指针同步运行（1个step），再次相遇时就为我们需要的节点。不要被题干中的pos给引导了
双指针技巧,当快慢指针相遇时，其中一个再去头节点，此时快慢指针同步运行（1个step），再次相遇时就为我们需要的节点。不要被题干中的pos给引导了
- 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)
# 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
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)
