本文共 1787 字，大约阅读时间需要 5 分钟。

双指针技术在链表和数组问题中的应用

在解决链表问题时，我们可以考虑使用双指针技术。双指针主要分为两类：一类是“快慢指针”，主要用于链表问题；另一类是“左右指针”，则更多用于数组或字符串问题。

快慢指针：主要应用于链表问题，常见的场景是判定链表是否包含环。

左右指针：主要用于数组或字符串问题，例如二分搜索。

判定链表是否含有环

要判断一个链表是否含有环，我们可以采用快慢指针技术。这种方法的基本思路是：

• 如果链表不含环，两个指针最终会同时遇到null，表示链表的终点。
• 如果链表含有环，快指针会比慢指针提前绕完环，两者会在某个节点相遇。

实现代码如下：

boolean hasCycle(ListNode head) {    if (head == null) return false;    List node slow = head;    List node fast = head;    while (slow != null && fast != null) {        slow = slow.next;        fast = fast.next.next;        if (slow == fast) return true;    }    return false;}

寻找环的起始位置

如果链表已经确认含有环，我们可以通过以下步骤找出环的起始位置：

代码实现如下：

List node findCycleStart(ListNode head) {    List node slow = head, fast = head;    while (slow != null && fast != null) {        slow = slow.next;        fast = fast.next.next;        if (slow == fast) break;    }    List node fast = head;    while (slow != fast) {        slow = slow.next;        fast = fast.next;    }    return slow;}

寻找无环单链表的中点

寻找单链表的中点可以采用以下方法：

代码实现如下：

List node findMidpoint(ListNode head) {    List node slow = head, fast = head;    while (fast != null && fast.next != null) {        fast = fast.next.next;        slow = slow.next;    }    return slow;}

寻找单链表的倒数第k个元素

要找出单链表的倒数第k个元素，可以采用以下方法：

代码实现如下：

List node findKthLast(ListNode head, int k) {    List node slow = head, fast = head;    // 使快指针提前走k步    for (int i = 0; i < k; i++) {        fast = fast.next;    }    // 同时让慢指针和快指针以相同速度前进    while (fast != null) {        slow = slow.next;        fast = fast.next;    }    return slow;}

以上方法通过快慢指针技术解决了多种链表问题。这种方法不仅时间复杂度优化到了O(n)，而且空间复杂度仅使用O(1)额外存储空间，适用于各种链表操作场景。