双指针法高效解决七道链表问题

双指针法在处理单链表相关问题时非常有效。以下是几个典型的应用场景：

1. 合并两个有序链表

2. 合并多个有序链表

3. 查找单链表的倒数第k个节点

4. 查找单链表的中点

5. 判断单链表是否包含环并找出环的起点

6. 判断两个单链表是否相交并找出交点

7. 反转链表

合并两个有序链表

这是最基础的链表操作之一，对应LeetCode第21题「合并两个有序链表」。

class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode* dummy = new ListNode(-1);
ListNode* p = dummy;
while (l1 && l2) {
if (l1->val val) {
p->next = l1;
l1 = l1->next;
} else {
p->next = l2;
l2 = l2->next;
}
p = p->next;
}
p->next = l1 ? l1 : l2;
return dummy->next;
}
};


代码中使用了「虚拟头结点」技巧，即 dummy 节点，这可以避免处理空指针的情况，简化代码逻辑。

合并多个有序链表

一种直观的方法是将链表两两合并，但这会导致较高的时间复杂度。更高效的解决方案是使用优先级队列（最小堆）。

class Solution {
public:
ListNode* mergeKLists(vector& lists) {
auto compare = [](ListNode* a, ListNode* b) { return a->val > b->val; };
priority_queue, decltype(compare)> pq(compare);
for (ListNode* head : lists) {
if (head) pq.push(head);
}
ListNode* dummy = new ListNode(-1);
ListNode* p = dummy;
while (!pq.empty()) {
ListNode* node = pq.top();
pq.pop();
p->next = node;
if (node->next) pq.push(node->next);
p = p->next;
}
return dummy->next;
}
};


通过使用优先级队列，我们可以在每次操作中获取当前最小的节点，从而高效地合并多个有序链表。

本文参考自博客园，作者：{BailanZ}，原文链接：https://www.cnblogs.com/BailanZ/p/16095523.html