def reverseList(self, head: ListNode) -> ListNode:
        cur = head
        prev = None
        while cur:
            cur.next, prev, cur = prev, cur, cur.next
        return prev

 def swapPairs(self, head):
        a, a.next = self, head
        while a.next and a.next.next:
            b,c = a.next, a.next.next
            a.next, b.next, c.next = c, c.next, b
            a = b
        return self.next

def hasCycle(self, head: ListNode) -> bool:
    # 快慢指针法
        fast = slow = head
        while fast and slow and fast.next:
            fast = fast.next.next
            slow = slow.next
            if (fast == slow):
                return True
        return False

def detectCycle(self, head: ListNode) -> ListNode:
    # 快慢指针不好使，快指针可能会跳过那个节点
    # 所以还是使用的缓存法，把走过的路缓存起来
        cur = head
        cache = set()
        while cur:
            if cur not in cache:
                cache.add(cur)
                cur = cur.next
            else:
                return cur
        return None

def isValid(self, s: str) -> bool:
         #堆栈的方式
        symbols = {'}':'{',']':'[',')':'('}
        stack = []
        for i in s:
            if i not in symbols:
                stack.append(i)
                # if stack为空意思是 如果栈还是空的就来一个右符号，则肯定是无效的
                # 或者是栈取出来的不一样
            elif not stack or symbols[i] != stack.pop():
                return False
        return not stack

    def __init__(self):
        self.q = []

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

    def pop(self) -> int:
        temp = self.q[-1]
        del self.q[-1]
        return temp

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

    def empty(self) -> bool:
        return not len(self.q)

    def __init__(self):
        self.s1 = []
        self.s2 = []

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

    def pop(self) -> int:
        if not len(self.s2):
            for _ in range(len(self.s1)):
                self.s2.append(self.s1.pop())
        return self.s2.pop()

    def peek(self) -> int:
        if not len(self.s2):
            for _ in range(len(self.s1)):
                self.s2.append(self.s1.pop())
        return self.s2[len(self.s2)-1]

    def empty(self) -> bool:
        return len(self.s1) == 0 and len(self.s2) == 0

# 排序的方式
def isAnagram(self, s: str, t: str) -> bool:
        return sorted(s) == sorted(t)

# hashMap 的方式
    def isAnagram(self, s: str, t: str) -> bool:
        voc1 = {}
        voc2 = {}
        for char in s:
            voc1[char] = voc1.get(char, 0) + 1
        for char in t:
            voc2[char] = voc2.get(char, 0) + 1
        return voc1 == voc2

def twoSum(self, nums: List[int], target: int) -> List[int]:
        res = {}
        # 遍历nums， 输出index和每个item值, 这里map中存的是数值的index，方便返回
        for i, item in enumerate(nums):
            if (target-item) not in res:
                res[item] = i
            else:
                return [res[target-item], i]
        return []

def threeSum(self, nums):
    nums.sort()
    res = set()
    for i,item in enumerate(nums[:-2]):
        # 此判断为了能快速判断，若item与前一位值相同则继续循环
        # 因为如果前面相同值有解，后面item的解一定与前面的相同，要求是答案中是不重复的，所以可以排除不遍历
​        if i >= 1 and item == nums[i-1]:
​            continue
​        d = {}
​        for item2 in nums[i+1:]:
​            if item2 not in d:

                # 这里的处理方式同两数之和，前2个数的负数就是第3个解，3数值和为0.
​                d[-item-item2] = 1
​            else:
​                res.add((item, -item-item2, item2))
​    return map(list, res)

def isValidBST(self, root: TreeNode) -> bool:        
        self.prve = None
        def isBST(root):
            if not root:
                return True
            if not isBST(root.left):
                return False 
            # 这里为什么要小于 前继节点的值？
            # 因为这是中序遍历，会把左子树全部走完才会走到每个树的根节点，所以prve一定是比根节点小的值，因为都是左子树嘛
            # 那么这里一定是更节点 > prve的值
            if self.prve and self.prve.val >= root.val:
                return False
            # 这里赋值的原因是，要拿根节点与右子树比较
            self.prve = root 
            return isBST(root.right)
        return isBST(root)

 def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        # 简单递归
        def lower(root, p, q):
            if not root or root == p or root == q : return root
            left = lower(root, p,q) # 结果是p 或 q 或叶子节点
            right = lower(root, p ,q)
            if not left: return right # 如果左子树没有结果，结果一定在右边
            if not right: return left # 同理
            if left and right : return root # 如果左右子树都有值，说明当前节点就是左右子树的共同根节点
        return lower(root, left, right)

def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        # 排序递归
        if  root.val< p and root.val< q:
            return lowestCommonAncestor(root.right, p,q)
        if  root.val> p and root.val> q:
            return lowestCommonAncestor(root.left, p,q)
        if  root.val>p and root.val < q:
            return root

# 同上题简单递归，因为此题无序，无法使用排序逻辑
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        def lowest(root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
            # 此处如果root是空，也可以返回，表示后续没找到，走8，9行判断
            if not root or root == p or root == q: return root
            left = lowest(root.left, p, q)
            right = lowest(root.right, p, q)
            if not left: return right
            if not right:return left
            if left and right: return root
        return lowest(root, p, q)

 # 使用递归方式,分治
    def myPow(self, x: float, n: int) -> float:
        if not n : return 1
        if n < 0 : return (1 / self.myPow(x, -n))
        if n %2 : # 奇数
            return x * self.myPow(x, n-1)
        return self.myPow(x*x, n/2) # 偶数

def majorityElement(self, nums: List[int]) -> int:

    # 摩尔投票法， 当一个数的重复次数超过数组长度的一半，每次将两个不相同的数删除，最终剩下的就是要找的数。
        res = 0
        count = 0
        for item in nums:
            if count == 0:
                res = item
                count = 1
            elif item == res:
                count += 1
            else:
                count -= 1
        if count > 0: return res

def majorityElement(self, nums: List[int]) -> int:
    # 哈希法
        res = {}
        maxItem = 0
        maxNums = 0
        for item in nums:
            res[item] = res.get(item, 0) + 1
        for item, value in res.items():
            if maxNums < value : 
                maxItem = item
                maxNums = value
        return maxItem

def levelOrder(self, root: TreeNode) -> List[List[int]]:   
        # BFS 用队列
        queue = []
        queue.append(root)
        result = []
        while queue:
            size = len(queue)
            current_level = []
            for _ in range(size):
                node = queue.pop(0)
                current_level.append(node.val)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            result.append(current_level)
        return result
     

def levelOrder(self, root: TreeNode) -> List[List[int]]:   
        # DFS用栈
        result = []
        def dfs(node, level):
            if not node: return []
            if len(result) < level+1:
                result.append([])
            result[level].append(node.val)
            dfs(node.left, level+1)
            dfs(node.right, level+1)
        dfs(root,0)
        return result

# 2的幂次方 只有一位是1，其他全是0， 所以打掉1之后 就是0了
def isPowerOfTwo(self, n: int) -> bool:
        if n != 0 and n&(n-1) == 0:
            return True
        else:
            return False