算法题常用模版

链表

两个问题：

1. 什么时候需要设置一个 dummy 结点？

   当需要修改链表结构时基本都用 dummy

   当头结点可能会发生改变时，设置 dummy 结点。dummy 结点就是一个指向头结点的虚拟空节点，最大的作用就是不用去处理特判改变对象为头结点时的特殊情况。另外，如果题目要求返回头结点，可以方便地直接返回 dummy.next 。

2. 什么时候用 while cur，什么时候用 while cur.next ？

   当循环为 while cur 时，最后一次进入循环时 cur 位于尾结点，循环结束后 cur 为 None；

   当循环为 while cur.next 时，最后一次进入循环时 cur 位于倒数第二个结点，循环结束后 cur 为尾结点。

   具体题目我们只要想一想我们要让最后一次循环体发生时的边界是什么来判断即可。

• 反转链表
• 快慢指针
• 合并两个升序链表

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

反转链表（迭代）

def reverseList(head: Optional[ListNode]) -> Optional[ListNode]:
    prev, curr = None, head
    while curr:
        nxt = curr.next
        curr.next = prev
        prev = curr
        curr = nxt
    return prev

快慢指针

• 快指针先走 n 步，慢指针再走

  19. 删除链表的倒数第 N 个结点

  删除操作需要找到被删除结点的前一个结点即可，因此可以转化为：找链表的第 L-N 个结点（这里完全不用想下标是啥，统一按照“第几个”来想）。

  此时我们自然可以先遍历一次链表计算出 L，再遍历一次找到目标结点，但更巧妙的方法是用快慢指针：快指针先走 N 步，之后快慢指针一起每次走一步，直到快指针走到最后一个结点。

  可以这么想：

  • 由于有可能会删除头结点，因此首先添加一个 dummy 结点；

  • 添加了 dummy 后，链表有 L+1 个结点，从 dummy 开始，需要走 L 步到达尾结点；

  • 我们需要找的结点变成了第 L-N+1 个结点，从 dummy 开始，需要走 L-N 步到达；

  • 快指针先走 N 步，还需要走 L-N 步到达尾结点，因此慢指针也要走 L-N 步，此时慢指针位于第 L-N+1 个结点，正好满足。

  关键之处在于要想清楚“走几步”和“到达第几个结点”之间的关系。因为我们最熟悉和喜欢的是“循环n次”，也就是“走几步”，搞清楚这个关系后，我们可以自然的写 for _ in range(n) 了。

• 快指针和慢指针同时走，快指针每次走多步

  876. 链表的中间结点

  找中间结点是快慢指针的经典应用，主要不好想的点在于链表可能有奇数个或偶数个结点，当结点个数为奇数时，中间结点为第 $\frac{L+1}{2}$ 个；当结点个数为偶数时，中间结点为第 $\frac{L}{2}$ 和第 $\frac{L}{2}+1$ 个，但题目要求为找第二个中间结点。

  首先快慢指针都从 head 出发，快指针每次走两步，慢指针每次走一步，直到快指针走到尾结点或者 None（即尾结点的下一个），此时慢指针指向的就是中间结点（总结点个数为偶数时是第二个）。

  def middleNode(head: Optional[ListNode]) -> Optional[ListNode]:
      slow = fast = head
      while fast and fast.next:
          slow = slow.next
          fast = fast.next.next
      return slow

• 套圈问题

  142. 环形链表 II

  用快慢指针可以方便判断链表是否有环：初始时快慢指针都在 head，快指针每次走两步，慢指针每次走一步（跟找中点一样），如果链表有环，那么一定有一刻快慢指针相等（停留在环上的某个结点，相当于快指针套了慢指针 n 圈）。

  但如果我们想找环的第一个结点该怎么办呢？我们只能保证快慢指针相遇处位于环上，但不一定是第几个。其实这是很简单的小学数学：设从头到环需要走 $a$ 步，绕环一圈要走 $c$ 步，从头结点到相遇位置，慢指针一共走了 $b$ 步，那么快指针就走了 $2*b$ 步。由于快指针和慢指针相遇是因为快指针在环上把慢指针套圈了，因此 $b=kc, k\in N$，慢指针位置和环入口处的距离就是 $kc - a$，因此慢指针再走 $a$ 步就一定会回到环入口处。我们虽然不知道 $a$ 等于多少，但只要让一个新的指针指向头结点，和慢指针一起走，每次都走一步，当它们第一次相遇时的位置就一定是环入口结点。

  说了这么多，其实就两步：第一步让快慢指针相遇后停下（和单纯判断环一样），第二步让指向头结点的指针和慢指针同步走，第一次相遇的位置就是答案。

  

def detectCycle(head: Optional[ListNode]) -> Optional[ListNode]:
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            m = head
            while m is not slow:
                m = m.next
                slow = slow.next
            return m
    return None

合并两个升序链表

def mergeTwoLists(l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
    dummmy = ListNode()
    prev = dummmy
    while l1 and l2:
        if l1.val <= l2.val:
            prev.next = l1
            l1 = l1.next
        else:
            prev.next = l2
            l2 = l2.next
        prev = prev.next
    prev.next = l1 or l2
    return dummmy.next

二分

二叉树

二叉树的遍历