算法题回顾：双指针链表系列集锦
1，合并两个有序链表
思路
- 创建一个指向空的新链表，用来存储合并后的链表，p指针指向该链表。
- 创建双指针，分辨指向两个链表，用p1, p2表示
- while循环，依次判断两个指针指向数据的大小，将最小值赋值在p指针的当前值。将最小值的指针指向下一个节点，将p指针指向下一个节点。当p1或p2指向空指针时候退出while循环
- 判断如果p1指针不为空，将p->next指向p1->next
- 判断如果p2指针不为空，将p->nex指向p2->next
代码
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
// 虚拟头结点
ListNode* dummy = new ListNode(-1), *p = dummy;
ListNode* p1 = l1, *p2 = l2;
while (p1 != NULL && p2 != NULL) {
// 比较 p1 和 p2 两个指针
// 将值较小的的节点接到 p 指针
if (p1->val > p2->val) {
p->next = p2;
p2 = p2->next;
} else {
p->next = p1;
p1 = p1->next;
}
// p 指针不断前进
p = p->next;
}
if (p1 != NULL) {
p->next = p1;
}
if (p2 != NULL) {
p->next = p2;
}
return dummy->next;
}
2， 单链表的分解
给定一个链表的头节点head,和一个特定值 x，对链表进行分隔，使所有小于x的节点都放在x节点之前，大于等于x的放在x节点之后。保留两个分区中每个节点的相对位置。
思路
- 创建两个链表，分别存放小于x的数，和大于等于x的数的节点，指针为p1,p2
- 合并p1和p2的节点即为所求。
注意代码中每个while循环都先把p->next赋给tmp新链表，然后把p->next节点置为nullptr，是因为每次都是把p指针直接赋值给了p1->next，或者p2->next。为了防止p1,p2的链表指向混乱的p节点，所以需要把p->next节点置为nullptr
代码
ListNode* partition(ListNode* head, int x) {
// 存放小于 x 的链表的虚拟头结点
ListNode* dummy1 = new ListNode(-1);
// 存放大于等于 x 的链表的虚拟头结点
ListNode* dummy2 = new ListNode(-1);
// p1, p2 指针负责生成结果链表
ListNode* p1 = dummy1, * p2 = dummy2;
// p 负责遍历原链表，类似合并两个有序链表的逻辑
// 这里是将一个链表分解成两个链表
ListNode* p = head;
while (p != nullptr) {
if (p->val >= x) {
p2->next = p;
p2 = p2->next;
} else {
p1->next = p;
p1 = p1->next;
}
// 断开原链表中的每个节点的 next 指针
ListNode* temp = p->next;
p->next = nullptr;
p = temp;
}
// 连接两个链表
p1->next = dummy2->next;
return dummy1->next;
}
3， 合并k个有序链表
给一个链表数组，每个链表都是升序排列。请将所有链表合并为一个升序链表，并返回。
思路
- 创建一个最小堆，把每个链表的头节点存入堆
- while循环判断，每次从堆中取出一个当前最小值，把节点放在结果链表中。然后如果取出最小值的链表下一个节点不为空，就将其指向下一个节点，再放入到最小堆中。当最小堆中没有链表时候，退出while循环。
时间复杂度： O（Nlogk)， k是链表的条数，N是这些链表的节点总数。
代码
ListNode* mergeKLists(vector<ListNode*>& lists) {
if (lists.empty()) return nullptr;
// 虚拟头结点
ListNode* dummy = new ListNode(-1);
ListNode* p = dummy;
// 优先级队列，最小堆
priority_queue<ListNode*, vector<ListNode*>, function<bool(ListNode*, ListNode*)>> pq(
[] (ListNode* a, ListNode* b) { return a->val > b->val; });
// 将 k 个链表的头结点加入最小堆
for (auto head : lists) {
if (head != nullptr) {
pq.push(head);
}
}
while (!pq.empty()) {
// 获取最小节点，接到结果链表中
ListNode* node = pq.top();
pq.pop();
p->next = node;
if (node->next != nullptr) {
pq.push(node->next);
}
// p 指针不断前进
p = p->next;
}
return dummy->next;
}4， 求单链表的倒数第k个节点
基本版本：遍历两遍链表，第一遍 知道链表的长度n,第二遍，倒数第k个节点，就是正数第n-k+1个节点，输出第n-k+1个节点。
双指针版本：
- 常见第一个指针p1，并走到k个节点，
- 然后创建第2个指针p2， p2指向头指针
- p1和p2指针同步向next前进，当p1指针指向原始链表p的末尾nullptr时候，p2恰好走到第n-k+1的位置。
代码
// 返回链表的倒数第 k 个节点
ListNode* findFromEnd(ListNode* head, int k) {
ListNode* p1 = head;
// p1 先走 k 步
for (int i = 0; i < k; i++) {
p1 = p1 -> next;
}
ListNode* p2 = head;
// p1 和 p2 同时走 n - k 步
while (p1 != nullptr) {
p2 = p2 -> next;
p1 = p1 -> next;
}
// p2 现在指向第 n - k + 1 个节点，即倒数第 k 个节点
return p2;
}拓展，当需要删除链表的倒数第N个节点时候，可以直接用上面代码先找到倒数第n+1个节点x，然后把x->next指针指向x->next->next即可。
5, 求单链表的中点
思路
同理，创建两个指针slow, fast分别指向链表头节点head。
slow每次前进一步，fast每次前进2步，当fast走到head链表的末尾时候，slow就在链表的中点位置。
注意：如果链表中点有两个，则会返回靠后面的那个节点。
代码
ListNode* middleNode(ListNode* head) {
// 快慢指针初始化指向 head
ListNode* slow = head;
ListNode* fast = head;
// 快指针走到末尾时停止
while (fast != nullptr && fast->next != nullptr) {
// 慢指针走一步，快指针走两步
slow = slow->next;
fast = fast->next->next;
}
// 慢指针指向中点
return slow;
}6，判断链表是否包含环,以及环的起点
思路
还是通过快慢指针实现。slow指针前进一步，fast前进两步。
如果fast指针最终遇到空指针，说明链表中没有环；如果fast最终和slow相遇，那就是fast超过了slow一圈，说明链表中有环。
bool hasCycle(ListNode* head) {
// 初始化快慢指针，指向头结点
ListNode* slow = head;
ListNode* fast = head;
// 快指针到尾部时停止
while (fast && fast->next) {
// 慢指针走一步，快指针走两步
slow = slow->next;
fast = fast->next->next;
// 快慢指针相遇，说明含有环
if (slow == fast) {
return true;
}
}
// 不包含环
return false;
}判断环的起点：只需要在fast和slow相遇时候，将slow节点重新指向头节点，然后slow和fast指针开始同步前进，当再次相遇时候，即为环的起始节点。
如下示意图，首次相遇，slow走了k步， fast走了2k步，环的长度是k, 假设相遇节点离环的起点距离是n, 则从头节点到slow位置是k, 从头节点到环起点begin是k-n。 环的长度减去环起点到slow的距离也是-n。所以从首次相遇的地方，重新让slow指向头节点，fast和slow同步前进，当再次相遇时候，即为环的起始节点。
代码
ListNode* detectCycle(ListNode* head) {
ListNode* fast = head;
ListNode* slow = head;
while (fast != nullptr && fast->next != nullptr) {
fast = fast->next->next;
slow = slow->next;
if (fast == slow) break;
}
// 上面的代码类似 hasCycle 函数
if (fast == nullptr || fast->next == nullptr) {
// fast 遇到空指针说明没有环
return nullptr;
}
// 重新指向头结点
slow = head;
// 快慢指针同步前进，相交点就是环起点
while (slow != fast) {
fast = fast->next;
slow = slow->next;
}
return slow;
}7， 判断两个链表是否相交
如下图，给链表A为a1->a2->c1->c2, 链表B为 b1->b2->b3->c1->c2，如何判断A，B是否相交？
思路
难点在于由于两条链表的长度可能不同，两条链表之间的节点无法对应。所以解决问题的关键是通过某种方式，让p1,p2分别指向A，B，让其能够同时到达节点c1。
我们可以让 p1 遍历完链表 A 之后开始遍历链表 B，让 p2 遍历完链表 B 之后开始遍历链表 A，这样相当于「逻辑上」两条链表接在了一起。
如果这样进行拼接，就可以让 p1 和 p2 同时进入公共部分，也就是同时到达相交节点 c1：
代码
// 求链表的交点
ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
// p1 指向 A 链表头结点，p2 指向 B 链表头结点
ListNode *p1 = headA, *p2 = headB;
while (p1 != p2) {
// p1 走一步，如果走到 A 链表末尾，转到 B 链表
if (p1 == nullptr) p1 = headB;
else p1 = p1->next;
// p2 走一步，如果走到 B 链表末尾，转到 A 链表
if (p2 == nullptr) p2 = headA;
else p2 = p2->next;
}
return p1; // 返回交点
}另外一种思路是，首先得到A，B的链表长度，然后谁长，谁先走n步，用于使其同时到达最后一个节点。然后A，B同步前进，当相同时候退出程序，返回true，或者同时走到最后时候退出，返回false。
代码
ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
int lenA = 0, lenB = 0;
// 计算两条链表的长度
for (ListNode *p1 = headA; p1 != nullptr; p1 = p1->next) {
lenA++;
}
for (ListNode *p2 = headB; p2 != nullptr; p2 = p2->next) {
lenB++;
}
// 让 p1 和 p2 到达尾部的距离相同
ListNode *p1 = headA, *p2 = headB;
if (lenA > lenB) {
// p1 先走过 lenA-lenB 步
for (int i = 0; i < lenA - lenB; i++) {
p1 = p1->next;
}
} else {
// p2 先走过 lenB-lenA 步
for (int i = 0; i < lenB - lenA; i++) {
p2 = p2->next;
}
}
// 看两个指针是否会相同，p1 == p2 时有两种情况：
// 1、要么是两条链表不相交，他俩同时走到尾部空指针
// 2、要么是两条链表相交，他俩走到两条链表的相交点
while (p1 != p2) {
p1 = p1->next;
p2 = p2->next;
}
return p1;
}参考：双指针技巧秒杀七道链表题目 :: labuladong的算法小抄