链表算法
双指针操纵链表
双指针共有以下比较常用的用法:
1、合并两个有序链表
2、合并 k 个有序链表
3、寻找单链表的倒数第 k 个节点
4、寻找单链表的中点
5、判断单链表是否包含环并找出环起点
6、判断两个单链表是否相交并找出交点1.合并两个有序链表
解题思路:
由于两个链表自身是有序的, 因此只需两个指针p1, p2分别遍历两个链表l1, l2,
根据大小分别指向将链表当前值连起来.
但一般便于理解, 代码中还用到一个链表的算法题中是很常见的「虚拟头结点」技巧，也就是 dummy 节点。你可以试试，如果不使用 dummy 虚拟节点，代码会复杂很多，而有了 dummy 节点这个占位符，可以避免处理空指针的情况，降低代码的复杂性
具体效果见下图:
类似题目:
2.合并 k 个有序链表
解题思路:
合并 k 个有序链表 是 合并两个有序链表 的超集. 原理类似,
但两个有序序列可以用代码手写排序, k 个有序链表时无法手写,
但很明显能想到的思路是用一个指针数组来维护长度为 k 的指针数组, 数组中的指针分别指向 k 个链表中的当前位置,
如何快速高效的找出指针数组中的最小节点, 那么此解就是最优解.
此处选择的是 优先级队列(即最小堆数组) (opens in a new tab) , 把链表节点放入一个最小堆，就可以快速高效的找出指针数组中的最小节点：
时间复杂度: 优先队列 pq 中的元素个数最多是 k，所以一次 poll 或者 add 方法的时间复杂度是 O(logk)；所有的链表节点都会被加入和弹出 pq，所以算法整体的时间复杂度是 O(Nlogk)，其中 k 是链表的条数，N 是这些链表的节点总数。
类似题目:
3、寻找单链表的倒数第 k 个节点
解题思路:
两个指针 p1, p2, 先让 p2 比 p1 多走 k 步, 然后让 p1, p2 在同时走即可, 直到 p2 走到结束节点.
类似题目:
4、寻找单链表的中点
解题思路:
与 寻找单链表的倒数第 k 个节点 比较类似, 两个指针 p1, p2, p1 走一步, p2 走两步, 直到 p2 走到结束节点.
类似题目:
5、判断链表是否包含环
解题思路:
与 寻找单链表的中点 比较类似, 两个指针 p1, p2, p1 走一步, p2 走两步, 直到 p2 走到结束节点(无环)或者 p1 和 p2 相遇.
不一定非要
p1走一步,p2走两步, 事实上 只要p1和p2走的步调不一致, 那么最终一定会相遇 (如果有环).
类似题目:
6、判断两个单链表是否相交并找出交点
解题思路: 一句话描述就是将两个数组练起来, 分别遍历, 终点值一样就是相交, 不一样就是不想交.
这边贴三张图, 一目了然
类似题目:
