LinkedList

链表

链表操作基本都需要prev指针, 搭配dummy用于操作头节点.

删除

• 203. 移除链表元素

• 83. 删除排序链表中的重复元素

• 82. 删除排序链表中的重复元素 II

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

交换

• 206. 反转链表
• 24. 两两交换链表中的节点
• 25. K 个一组翻转链表

插入、归并

• 21. 合并两个有序链表
• 23. 合并 K 个升序链表
• 86. 分隔链表

取中点

876. 链表的中间结点

综合

• 143. 重排链表
• 234. 回文链表
• 61. 旋转链表
• 92. 反转链表 II
• 109. 有序链表转换二叉搜索树

特殊位置

通常搭配多指针使用

• 19. 删除链表的倒数第 N 个结点
• 141. 环形链表
• 142. 环形链表 II f = 2 * nb, s = nb, 交点：a + nb 。 所以用个指针再走a即可。
• 160. 相交链表

排序

插入排序

归并排序：注意找中点时的起点和循环终止条件的组合。

• 148. 排序链表

静态链表

• 287. 寻找重复数

技巧

• 237. 删除链表中的节点

分析

取中点

876. 链表的中间结点

区分起点，其实这两种只是置换了下节点数量的奇偶性。

• 从dummy开始
• 从第一个节点开始

区分循环终止条件，注意这两种，在偶数情况下都是找到中点左边节点。

• fast->next != nullptr && fast->next->next != nullptr 奇数找到中点前置节点
• fast != nullptr && fast->next != nullptr 奇树找到中点。

总结

• 从dummy开始：两种都不用特判空，根据要求使用即可。
• 从第一个节点开始：注意，从第一节点开始和 fast->next != nullptr && fast->next->next != nullptr 一起时，fast可能初始化为nullptr，注意特判。所以不推荐这种组合。

从dummy开始

这是逻辑最清晰的一种方式

如果循环终止条件为

终止条件： fast->next != nullptr && fast->next->next != nullptr

• 奇数情况下，会到中点前置节点。

• 偶数情况下，会找到中点左边节点。

终止条件 fast != nullptr && fast->next != nullptr

• 奇数情况下，会到中点。

• 偶数情况下，会到中点左边节点。

从第一个节点开始

注意第一个节点判空，奇偶情况和从dummy开始的情况对调即是答案。