链表的算法题中很常见的技巧:
- 添加虚拟头结点,即dummy结点。当需要创造一条新链表的时候,可以使用虚拟头节点简化边界情况的处理。
- 例如:LeetCode21. 合并两个有序链表,让两条有序链表合并成一条新的有序链表,需要创造一条新的链表。
- 例如,LeetCode86. 分隔链表,把一条链表分解成两条链表,也是在创造新的链表。
- 让一个指针先走几步,然后让第二个指针和第一个指针同时走,直至第一个指针为NULL。
- 还是添加一个dummy结点,方便操作
- 例如:LeetCode19. 删除链表的倒数第N个结点
- 例如:LeetCode876. 链表的中间结点
- 例如:LeetCode19. 删除链表的倒数第N个结点,获得单链表的倒数第N+1个结点
- 如果操作过程中会导致头节点变化,则也应该设置一个dummy头节点保证头节点不会改变。
- 例如:LeetCode24. 两两交换链表中的节点
- 例如:LeetCode25. K个一组翻转链表
- 例如:LeetCode92. 反转链表II