Linked List

双指针， 包括快慢指针 Leetcode 24. Swap Nodes in Pairs

双向链表求交点 Leetcode 1650. Lowest Common Ancestor of a Binary Tree III

Reversed linked list

Leetcode 206. Reverse Linked List

iteration

def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
    prev = None # dummy node
    cur = head
    while cur is not None:
        nex = cur.next
        cur.next = prev
        prev = cur
        cur = nex
    return prev

recursion

def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
    if not head or not head.next:
        return head
    new_next_node = self.reverseList(head.next)
    head.next.next = head
    head.next = None
    return new_next_node

Leetcode 25. Reverse Nodes in k-Group

recursion

def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
    dummy = ListNode(-1)
    dummy.next = head
    pre, end = dummy, dummy

    while end is not None:
        for i in range(k):
            if end is None:
                break
            end = end.next

        if end is None:
            break

        # pre, start, ...end, nex
        start = pre.next
        nex = end.next
        end.next = None
        pre.next = self.reverse(start)
        start.next = nex
        pre, end = start, start

    return dummy.next

def reverse(self, cur):
    pre = None
    while cur is not None:
        nex = cur.next
        cur.next = pre
        pre = cur
        cur = nex
    return pre

Stack

单调递增栈可以找到元素向左遍历第一个比它小的元素。比如数组 [2 1 4 6 5]，刚开始2入栈，数字1入栈的时候，发现栈顶元素2比较大，将2移出栈，此时 1入栈。那么2和1都没左起比自身小的数字。然后数字4入栈的时候，栈顶元素1 小于4，于是1就是4左起第一个小的数字。此时栈里有1和4，然后数字6入栈的时 候，栈顶元素4小于6，于是4就是6左起第一个小的数字。此时栈里有1，4，6， 然后数字5入栈的时候，栈顶元素6大于5，将6移除，此时新的栈顶元素4小于5， 那么4就是5左起的第一个小的数字，最终栈内数字为 1，4，5。

Leetcode 768. Max Chunks To Make Sorted II Leetcode 42. Trapping Rain Water Largest Rectangle in Histogram Remove K Digits Leetcode 496：下一个更大元素 I（超详细的解法！！！） Leetcode 503：下一个更大元素 II（超详细的解法！！！） Leetcode 739：每日温度（超详细的解法！！！） Leetcode 901：股票价格跨度（超详细的解法！！！） Leetcode 239：滑动窗口最大值（超详细的解法！！！）(更明确为区间最大元素问题) Leetcode 1762. Buildings With an Ocean View

Array

subarray: A subarray is a contiguous non-empty sequence of elements within an array.

String

Palindromic substring

Manacher’s Algorithm 马拉车算法 开头结尾加$，中间每个字符间加# bob -> $#b#o#b#$ 最长子串的长度是半径减1，起始位置是中间位置减去半径再除以2 Leetcode 5. Longest Palindromic Substring