给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ，则返回 true 。 否则，返回 false 。

• https://leetcode-cn.com/problems/linked-list-cycle

快慢指针，如fast指针能遇到NULL则无法成环，当fast和slow相遇则说明成环。

这里最难搞得是理解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)

要不赞赏一下?

微信

支付宝

PayPal

Bitcoin