美团算法高频题面经：反转链表、两数之和、有效括号、最长子串、合并区间

上篇聊完Compose动画和重组机制，这篇回到算法。美团算法面试的Medium题集中在链表、哈希表、栈、滑动窗口和区间合并这几类。跟字节相比，美团不考Hard但要求代码无Bug、边界考虑周全、复杂度分析清晰。

今天8道题覆盖美团算法面试高频题型。

Q1：反转链表（LeetCode 206）

问题：给单链表头节点，反转链表并返回新头节点。

迭代法：三个指针prev、curr、next。遍历链表，每次把curr.next指向prev，然后三个指针前进。遍历完毕prev就是新头。O(n)时间O(1)空间。

ListNode reverseList(ListNode head) { ListNode prev = null, curr = head; while (curr != null) { ListNode next = curr.next; curr.next = prev; prev = curr; curr = next; } return prev; }

递归法：递归到末尾，回溯时反转指针。head.next.next = head; head.next = null。O(n)时间O(n)空间（递归栈）。

追问：反转链表的部分区间怎么做（LeetCode 92）？定位到区间起点，对区间内节点做反转，再把断开的指针接上。注意区间起点是头节点的特殊情况。