labuladong 的算法秘籍-读书笔记-双指针技巧秒杀七道链表题目

1、合并两个有序链表

解题思路

使用虚拟头结点

遍历两个链表，将数值小的节点加入虚拟头节点中。直到某个链表为空。将另一个链表加入。

返回虚拟头节点的下一个节点。

当你需要创造一条新链表的时候，可以使用虚拟头结点简化边界情况的处理

2、单链表的分解

解题思路

创建两个虚拟头节点，分别存放小于链表和大于等于链表

遍历链表，小于的加入链表，大于等于的加入另一个链表

遍历两个链表虚拟头节点的下一个节点

然后连接两个链表

3、合并k个有序链表

1的加强型，其实先从k个链表中找到第一个最小的就行，可以使用最小堆。然后使用1的套路

4、单链表的倒数第k个节点 删除链表的倒数第k个节点

双指针，第一个指针先走k步，然后第二个指针指向头，两个指针相差k。两个指针同时往前走。

当第一个指针到尾部的时候，第二个指针刚好在倒数第k个节点。

5、单链表的中点

快慢指针，一个指针走1步，一个指针走2步。当走两步的指针到尾部时，另一个指针就到中间。

6、判断链路是否包含环

快慢指针，慢指针走1步，快指针走2步，如果快指针最后指向空，说明没有环，如果快慢指针相遇，说明有环。

7、两个链表是否相交

将两个链表相连，同时遍历两个链表就可以同时进入公共部分

具体代码见知乎

https://zhuanlan.zhihu.com/p/599759514