class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
        l1, l2 = headA, headB
        while l1 != l2:
            # 当 l1 到达尾部时，重新指向 headB；当 l2 到达尾部时，重新指向 headA
            l1 = headB if not l1 else l1.next
            l2 = headA if not l2 else l2.next
        return l1

func getIntersectionNode(headA, headB *ListNode) *ListNode {
    l1, l2 := headA, headB
    for l1 != l2 {
        if l1 == nil {
            l1 = headB
        } else {
            l1 = l1.Next
        }

        if l2 == nil {
            l2 = headA
        } else {
            l2 = l2.Next
        }
    }
    return l1
}

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if not root or root == q or root == p:
            return root
        
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)

        if left and right:
            return root
        
        if left or right:
            return left if left else right

func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
	if root == nil || root == p || root == q {
		return root
	}

	left := lowestCommonAncestor(root.Left, p, q)
	right := lowestCommonAncestor(root.Right, p, q)

	if left != nil && right != nil {
		return root
	}

	if left != nil {
		return left
	}
	return right
}

class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        front = head

        def recursive(cur):
            nonlocal front
            if cur:
                if not recursive(cur.next):
                    return False
                if front.val != cur.val:
                    return False
                front = front.next
            return True

        return recursive(head)

func isPalindrome(head *ListNode) bool {
    front := head

    var recursive func(cur *ListNode) bool
    recursive = func(cur *ListNode) bool {
        if cur == nil {
            return true
        }
        if !recursive(cur.Next) {
            return false
        }
        if front.Val != cur.Val {
            return false
        }
        front = front.Next
        return true
    }

    return recursive(head)
}

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        stk = []
        n = len(temperatures)
        res = [0] * n

        for i in range(n - 1, -1, -1):
            while stk and temperatures[stk[-1]] <= temperatures[i]:
                stk.pop()

            if stk:
                res[i] = stk[-1] - i

            stk.append(i)

        return res

func dailyTemperatures(temperatures []int) []int {
    n := len(temperatures)
    stk := make([]int, 0)
    res := make([]int, n)

    for i := n - 1; i >= 0; i -= 1 {
        for len(stk) > 0 && temperatures[stk[len(stk) - 1]] <= temperatures[i] {
            stk = stk[:len(stk) - 1]
        }
        if len(stk) > 0 {
            res[i] = stk[len(stk) - 1] - i 
        }
        stk = append(stk, i)
    }
    
    return res
}

class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root:
            return root
        
        root.left, root.right = root.right, root.left

        self.invertTree(root.left)
        self.invertTree(root.right)

        return root

func invertTree(root *TreeNode) *TreeNode {
    if root == nil {
        return root
    }

    root.Left, root.Right = root.Right, root.Left

    invertTree(root.Left)
    invertTree(root.Right)

    return root
}

class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        m, n = len(matrix), len(matrix[0])

        f = [[0] * (n + 1) for _ in range(m + 1)]
        res = 0

        for i in range(m):
            for j in range(n):
                if matrix[i][j] == "1":
                    f[i + 1][j + 1] = min(f[i][j + 1], f[i + 1][j], f[i][j]) + 1
                    if f[i + 1][j + 1] > res:
                        res = f[i + 1][j + 1]

        return res * res

func maximalSquare(matrix [][]byte) int {
	m, n := len(matrix), len(matrix[0])

	f := make([][]int, m+1)
	for i := 0; i <= m; i += 1 {
		f[i] = make([]int, n+1)
	}

	res := 0

	for i := 0; i < m; i += 1 {
		for j := 0; j < n; j += 1 {
			if matrix[i][j] == '1' {
				f[i+1][j+1] = min(f[i][j+1], f[i+1][j], f[i][j]) + 1
				if f[i+1][j+1] > res {
					res = f[i+1][j+1]
				}
			}
		}
	}

	return res * res
}

func min(a, b, c int) int {
	if a < b {
		if a < c {
			return a
		}
	}
	if b < c {
		return b
	}
	return c
}

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        def qs(q, l, r, k):
            if l >= r:
                return 

            i, j, x = l - 1, r + 1, q[l + r >> 1]
            while i < j:
                i += 1
                while q[i] < x:
                    i += 1
                
                j -= 1
                while q[j] > x:
                    j -= 1
                
                if i < j:
                    q[i], q[j] = q[j], q[i]
            
            if j < k:
                qs(q, j + 1, r, k)
            else:
                qs(q, l, j, k)

            # qs(q, i, j, k)
            # qs(q, j + 1, r, k)
        
        n = len(nums)
        k = n - k # n - 1 - k + 1
        qs(nums, 0, n - 1, k)
        
        return nums[k]

class Trie:
    def __init__(self):
        self.trie = {}

    def insert(self, word: str) -> None:
        cur = self.trie
        for ch in word:
            if ch not in cur:
                cur[ch] = {}
            cur = cur[ch]
        cur['#'] = True

    def search(self, word: str) -> bool:
        cur = self.trie
        for ch in word:
            if ch not in cur:
                return False
            cur = cur[ch]
        return cur['#'] if '#' in cur else False

    def startsWith(self, prefix: str) -> bool:
        cur = self.trie
        for ch in prefix:
            if ch not in cur:
                return False
            cur = cur[ch]
        return True

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        g = defaultdict(list)
        ind = defaultdict(int)

        for f, t in prerequisites:
            g[f].append(t)
            ind[t] += 1

        cnt = 0

        q = deque()
        for node in range(numCourses):
            if ind[node] == 0:
                q.append(node)
                cnt += 1

        while q:
            f = q.popleft()
            for nx in g[f]:
                ind[nx] -= 1
                if ind[nx] == 0:
                    cnt += 1
                    q.append(nx)

        return cnt == numCourses

func canFinish(numCourses int, prerequisites [][]int) bool {
	g := make(map[int][]int)
	ind := make(map[int]int)

	for _, pre := range prerequisites {
		f, t := pre[0], pre[1]
		g[f] = append(g[f], t)
		ind[t]++
	}

	cnt := 0
	q := list.New()

	for node := 0; node < numCourses; node++ {
		if ind[node] == 0 {
			q.PushBack(node)
			cnt++
		}
	}

	for q.Len() > 0 {
		f := q.Remove(q.Front()).(int)
		for _, nx := range g[f] {
			ind[nx]--
			if ind[nx] == 0 {
				cnt++
				q.PushBack(nx)
			}
		}
	}

	return cnt == numCourses
}

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # 递归基：如果 head 为空或只有一个节点，直接返回 head
        if not head or not head.next:
            return head
            
        # 递归反转后续链表
        newHead = self.reverseList(head.next)
        
        # 反转当前节点
        head.next.next = head  # 将 head 节点连接到反转后的链表末尾
        head.next = None       # 断开原来的链表连接

        return newHead  # 返回反转后的链表头

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        prev = None
        curr = head
        while curr:
            next_node = curr.next   # 暂存下一个节点
            curr.next = prev        # 将当前节点指向前一个节点
            prev = curr             # 更新 prev 为当前节点
            curr = next_node        # 更新 curr 为下一个节点
        
        return prev  # prev 是新的头节点

func reverseList(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}
	newHead := reverseList(head.Next)
	head.Next.Next = head
	head.Next = nil
	return newHead
}

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        def dfs(i, j):
            vis[i][j] = True
            for k in range(4):
                x, y = i + d[k][0], j + d[k][1]
                if x < 0 or x >= n or y < 0 or y >= m or vis[x][y] or grid[x][y] == "0":
                    continue
                dfs(x, y)

        n, m = len(grid), len(grid[0])
        d = [(-1, 0), (0, 1), (1, 0), (0, -1)]
        vis = [[False] * m for _ in range(n)]
        res = 0

        for i in range(n):
            for j in range(m):
                if not vis[i][j] and grid[i][j] == "1":
                    dfs(i, j)
                    res += 1
                    
        return res

func numIslands(grid [][]byte) int {
	n, m := len(grid), len(grid[0])
	d := [][2]int{{-1, 0}, {0, 1}, {1, 0}, {0, -1}}
	vis := make([][]bool, n)
	for i := range vis {
		vis[i] = make([]bool, m)
	}

	var dfs func(i, j int)
	dfs = func(i, j int) {
		vis[i][j] = true
		for _, dir := range d {
			x, y := i+dir[0], j+dir[1]
			if x < 0 || x >= n || y < 0 || y >= m || vis[x][y] || grid[x][y] == '0' {
				continue
			}
			dfs(x, y)
		}
	}

	res := 0
	for i := 0; i < n; i++ {
		for j := 0; j < m; j++ {
			if !vis[i][j] && grid[i][j] == '1' {
				dfs(i, j)
				res++
			}
		}
	}

	return res
}

class Solution:
    def rob(self, nums: List[int]) -> int:
        n = len(nums)

        f, s = 0, nums[0]
        for i in range(1, n):
            f, s = s, max(f + nums[i], s)

        return s

func rob(nums []int) int {
    f, s := 0, nums[0]

    for _, cur := range(nums[1:]) {
        f, s = s, max(s, f + cur)
    }

    return s
}

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        cnt = 0
        num = None 

        for nm in nums:
            if not cnt:
                num = nm 
            cnt += 1 if nm == num else -1
        
        return num

func majorityElement(nums []int) int {
    cnt, num := 0, 0
    for _, nm := range(nums) {
        if cnt == 0 {
            num = nm 
        }
        if nm == num {
            cnt += 1
        } else {
            cnt -= 1
        }
    }
    return num
}

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n = len(nums)
        pre, suf, res = [1] * n, [1] * n, [0] * n 

        for i in range(1, n):
            pre[i] = nums[i - 1] * pre[i - 1]
        for i in range(n - 2, -1, -1):
            suf[i] = nums[i + 1] * suf[i + 1]
        
        for i in range(n):
            res[i] = pre[i] * suf[i]
        
        return res

func productExceptSelf(nums []int) []int {
	n := len(nums)
	pre := make([]int, n)
	suf := make([]int, n)
	res := make([]int, n)

	for i := 0; i < n; i++ {
		pre[i] = 1
		suf[i] = 1
	}

	for i := 1; i < n; i++ {
		pre[i] = nums[i-1] * pre[i-1]
	}
	for i := n - 2; i >= 0; i-- {
		suf[i] = nums[i+1] * suf[i+1]
	}

	for i := 0; i < n; i++ {
		res[i] = pre[i] * suf[i]
	}

	return res
}

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

    def push(self, val: int) -> None:
        self.stk.append(val)
        self.mstk.append(min(val, self.mstk[-1] if self.mstk else val))

    def pop(self) -> None:
        self.stk.pop()
        self.mstk.pop()

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

    def getMin(self) -> int:
        return self.mstk[-1]

type MinStack struct {
	stk  []int
	mstk []int
}

func Constructor() MinStack {
	return MinStack{
		stk:  []int{},
		mstk: []int{},
	}
}

func (this *MinStack) Push(val int) {
	this.stk = append(this.stk, val)
	if len(this.mstk) == 0 {
		this.mstk = append(this.mstk, val)
	} else {
		minVal := this.mstk[len(this.mstk)-1]
		if val < minVal {
			minVal = val
		}
		this.mstk = append(this.mstk, minVal)
	}
}

func (this *MinStack) Pop() {
	this.stk = this.stk[:len(this.stk)-1]
	this.mstk = this.mstk[:len(this.mstk)-1]
}

func (this *MinStack) Top() int {
	return this.stk[len(this.stk)-1]
}

func (this *MinStack) GetMin() int {
	return this.mstk[len(this.mstk)-1]
}

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        mx, mn = 1, 1
        res = -inf

        for i, nm in enumerate(nums):
            mxv = max(nm, mx * nm, mn * nm)
            mnv = min(nm, mx * nm, mn * nm)
            mx, mn = mxv, mnv
            res = max(res, mx)
        
        return res

func maxProduct(nums []int) int {
	mx, mn := 1, 1
	res := nums[0]

	for _, nm := range nums {
		mxv := max(nm, mx*nm, mn*nm)
		mnv := min(nm, mx*nm, mn*nm)
		mx, mn = mxv, mnv
		if mx > res {
			res = mx
		}
	}

	return res
}

func max(a, b, c int) int {
	if a < b {
		a = b
	}
	if a < c {
		a = c
	}
	return a
}

func min(a, b, c int) int {
	if a > b {
		a = b
	}
	if a > c {
		a = c
	}
	return a
}

class Solution:
    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # 归并排序
        def sortFun(head, tail):
            if not head:
                return head
            if head.next == tail:
                head.next = None
                return head
                
            slow = fast = head

            while fast != tail:
                fast = fast.next
                slow = slow.next
                if fast != tail:
                    fast = fast.next
            mid = slow
            return merge(sortFun(head, mid), sortFun(mid, tail))

        def merge(h1, h2):
            dummy = ListNode(-1)
            cur = dummy
            while h1 and h2:
                if h1.val<=h2.val:
                    cur.next = h1
                    h1 = h1.next
                else:
                    cur.next = h2
                    h2 = h2.next
                cur = cur.next
            if h1:
                cur.next = h1
            if h2:
                cur.next = h2
            return dummy.next

        return sortFun(head, None)

// 合并两个有序链表
func merge(h1, h2 *ListNode) *ListNode {
	dummy := &ListNode{-1, nil}
	cur := dummy
	for h1 != nil && h2 != nil {
		if h1.Val <= h2.Val {
			cur.Next = h1
			h1 = h1.Next
		} else {
			cur.Next = h2
			h2 = h2.Next
		}
		cur = cur.Next
	}
	if h1 != nil {
		cur.Next = h1
	}
	if h2 != nil {
		cur.Next = h2
	}
	return dummy.Next
}

func sortList(head *ListNode) *ListNode {
	// 归并排序递归函数，tail 是右边界（不包含）
	var sortFun func(head, tail *ListNode) *ListNode
	sortFun = func(head, tail *ListNode) *ListNode {
		if head == nil {
			return head
		}
		if head.Next == tail {
			head.Next = nil
			return head
		}

		slow, fast := head, head
		for fast != tail {
			fast = fast.Next
			slow = slow.Next
			if fast != tail {
				fast = fast.Next
			}
		}
		mid := slow
		return merge(sortFun(head, mid), sortFun(mid, tail))
	}

	return sortFun(head, nil)
}

class DoubleLinkedList:
    def __init__(self, key = 0, value = 0):
        self.key = key
        self.value = value

        self.pre = None
        self.next = None

class LRUCache:

    def __init__(self, capacity: int):
        self.capacity = capacity
        self.size = 0
        self.cache = dict()

        self.head = DoubleLinkedList()
        self.tail = DoubleLinkedList()
        self.head.next = self.tail
        self.tail.pre = self.head

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        node = self.cache[key]
        self.moveToHead(node)
        return node.value

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            node = self.cache[key]
            node.value = value
            self.moveToHead(node)
        else:
            node = DoubleLinkedList(key, value)
            self.cache[key] = node
            if self.size < self.capacity:
                self.size += 1
            else:
                tail = self.removeTail()
                del self.cache[tail.key]
            self.addToHead(node)

        
    def removeNode(self, node):
        node.next.pre = node.pre
        node.pre.next = node.next
    
    def addToHead(self, node):
        node.next = self.head.next
        node.pre = self.head
        self.head.next.pre = node
        self.head.next = node
        
    def moveToHead(self, node):
        self.removeNode(node)
        self.addToHead(node)
    
    def removeTail(self):
        node = self.tail.pre
        self.removeNode(node)
        return node

type DoubleLinkedList struct {
	key, value int
	prev, next *DoubleLinkedList
}

type LRUCache struct {
	capacity   int
	size       int
	cache      map[int]*DoubleLinkedList
	head, tail *DoubleLinkedList
}

func Constructor(capacity int) LRUCache {
	head := &DoubleLinkedList{}
	tail := &DoubleLinkedList{}
	head.next = tail
	tail.prev = head

	return LRUCache{
		capacity: capacity,
		size:     0,
		cache:    make(map[int]*DoubleLinkedList),
		head:     head,
		tail:     tail,
	}
}

func (this *LRUCache) Get(key int) int {
	if node, ok := this.cache[key]; ok {
		this.moveToHead(node)
		return node.value
	}
	return -1
}

func (this *LRUCache) Put(key int, value int) {
	if node, ok := this.cache[key]; ok {
		node.value = value
		this.moveToHead(node)
	} else {
		node := &DoubleLinkedList{key: key, value: value}
		this.cache[key] = node
		if this.size < this.capacity {
			this.size++
		} else {
			tail := this.removeTail()
			delete(this.cache, tail.key)
		}
		this.addToHead(node)
	}
}

func (this *LRUCache) removeNode(node *DoubleLinkedList) {
	node.prev.next = node.next
	node.next.prev = node.prev
}

func (this *LRUCache) addToHead(node *DoubleLinkedList) {
	node.next = this.head.next
	node.prev = this.head
	this.head.next.prev = node
	this.head.next = node
}

func (this *LRUCache) moveToHead(node *DoubleLinkedList) {
	this.removeNode(node)
	this.addToHead(node)
}

func (this *LRUCache) removeTail() *DoubleLinkedList {
	node := this.tail.prev
	this.removeNode(node)
	return node
}

class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next:
            return None

        fast, slow = head, head
        while fast.next:
            fast = fast.next
            if fast.next:
                fast = fast.next
            slow = slow.next
            if fast == slow:
                break 
        if not fast.next:
            return None

        fast = head
        while fast != slow:
            fast = fast.next
            slow = slow.next
        
        return fast

func detectCycle(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return nil
	}

	slow, fast := head, head
	for fast != nil && fast.Next != nil {
		slow = slow.Next
		fast = fast.Next.Next
		if slow == fast {
			break
		}
	}

	if fast == nil || fast.Next == nil {
		return nil
	}

	fast = head
	for fast != slow {
		fast = fast.Next
		slow = slow.Next
	}

	return fast
}

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        if not head:
            return False 
        
        fast = slow = head
        while fast.next:
            fast = fast.next
            if fast.next:
                fast = fast.next
            slow = slow.next
            if fast == slow:
                break 
        
        if not fast.next:
            return False 
        
        return True