141.環(huán)形鏈表

算法（快慢指針）：

def hasCycle(self, head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True
    return False

155.最小棧

算法一：

class MinStack:
    def __init__(self):
        self.l = []

    def push(self, x: int) -> None:
        self.l.append(x)

    def pop(self) -> None:
        self.l.pop()

    def top(self) -> int:
        if not self.l:
            return 'error'
        else:
            return self.l[-1]

    def getMin(self) -> int:
        return min(self.l)

算法二：

class MinStack:
    def __init__(self):
        self.stack = []
        self.min = None
        
    def push(self, x: int) -> None:
        self.stack.append(x)
        if not self.min or self.min > x:
            self.min = x

    def pop(self) -> None:
        popItem = self.stack.pop()
        if len(self.stack) == 0:
            self.min= None
            return popItem

        if popItem == self.min:
            self.min == self.stack[0]
            for i in self.stack:
                if i < self.min:
                    self.min = i
        return popItem

    def top(self) -> int:
        return self.stack[-1]

    def getMin(self) -> int:
        return self.min

167. 兩數(shù)之和 II - 輸入有序數(shù)組

算法：

def twoSum(self, numbers, target):
    dic = {}           #用字典非常方便
    r = []
    for i in range(len(numbers)):
        if numbers[i] in dic.keys():       #如數(shù)組的值在字典中，說明之前的數(shù)已經(jīng)被目標(biāo)值減出來了
            r.append(dic[numbers[i]] + 1)
            r.append(i+1)
            return r           #返回下標(biāo)
        dic[target - numbers[i]] = i          #字典的key為減出來的數(shù)，
    return None

160.相交鏈表

算法一：

def getIntersectionNode(self, headA, headB):
    p1 = headA
    p2 = headB
    while p1 != p2:
        p1 = headB if p1 == None else p1.next    #遍歷兩個鏈表
        p2 = headA if p2 == None else p2.next
    return p1

分析：該算法是將兩個鏈表當(dāng)做兩條線段p1和p2，因此有p1+p2=p2+p1。例如
p1： A,E,C,H，
p2：B,S,W,C,H，
那么相加后分別為
A,E,C,H,B,S,W,C,H
B,S,W,C,H,A,E,C,H
可以看出，字母重合的地方就是本題所要求的交點。如果沒有交點，則會返回None

算法二：

def getIntersectionNode(self, headA, headB):
    lenA, lenB = 0, 0
    pA = headA
    pB = headB
    while pA:      #計算pA的長度
        pA = pA.next
        lenA += 1
    while pB:      #計算pB的長度
        pB = pB.next
        lenB += 1
    if lenA>lenB:      #對較長的鏈進行裁剪
        for i in range(lenA - lenB):
            pA = pA.next
    if lenB>lenA:      #對較長的鏈進行裁剪
        for i in range(lenA - lenB):
            pB = pB.next
    while pA!=pB:     #逐一比對
        pA = pA.next
        pB = pB.next
    return pA

分析：該算法利用了相交鏈表的最后幾個數(shù)字會重合的特點。首先求出單個鏈表的長度，對較長的鏈表進行裁剪，使得兩個鏈表長度一致，例如
p1： A,E,C,H，
p2：B,S,W,C,H，
對p2進行裁剪后得到
p1： A,E,C,H，
p2： S,W,C,H，
最后進行逐一比對，得到相交點，或者None。