嗯,校招笔试判卷子,到现在
先做一道水题吧:https://leetcode-cn.com/problems/linked-list-cycle/description/
除了用一个字典之类的容器存储之外,还可以利用快慢指针的方法,通过一次遍历就来解决这个问题:
一个走一步,一个走两部,如果俩个碰上来,那么就是有环,如果快指针先指向了None的话,就是没有环的
代码很直接:
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def hasCycle(self, head):
"""
:type head: ListNode
:rtype: bool
"""
if head == None or head.next == None:
return False
slow = head
fast = head.next
while fast != slow:
if fast == None or fast.next == None:
return False
else:
slow = slow.next
fast = fast.next.next
return True
网友评论