Day17

141. Linked List Cycle
     **思路：判断是不是循环链表？不等价于判断链表里是否有环？
     前一个问题：最后一点结点是否指向头结点。后一个问题：只要中间有一个重复出现了就是有环。但是用了额外的空间来存储。

class Solution(object):
    def hasCycle(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        if head == None or head.next == None:
            return False
        slow= fast = head
        while fast and fast.next :
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                return True
        return False

155. Min Stack

     
     

**思路：好难！！！！采用minstack和stack一样长度的方式来存储，这样可以简化pop（）部分的代码。

class MinStack(object):

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.stack = []
        self.mins = []

    def push(self, x):
        """
        :type x: int
        :rtype: void
        """
        min_val = self.getMin()
        if min_val==None or min_val>x:
            min_val = x
        self.mins.append(min_val)
        self.stack.append(x)

    def pop(self):
        """
        :rtype: void
        """
        self.mins.pop()
        return self.stack.pop()

    def top(self):
        """
        :rtype: void
        """
        return self.stack[-1]


    def getMin(self):
        """
        :rtype: void
        """
        if len(self.mins) == 0:
            return None
        return self.mins[-1]