在数据结构中，链表是一种常用的线性数据结构，其通过节点之间的指针连接构成，可以高效地进行插入和删除操作。与之相伴的双指针技术，是一种通过使用两个指针同步或非同步移动来解决问题的常见技巧，尤其在链表问题中应用广泛。本文将深入探讨链表的基本概念与双指针技巧，结合实际问题展示其在经典算法中的应用。

链表的基本概念

链表是一种由节点组成的数据结构，每个节点包含两个部分：数据域和指针域。数据域存储节点的值，指针域存储指向下一个节点的指针。

链表的类型主要包括：

• 单向链表：每个节点只指向下一个节点。
• 双向链表：每个节点既指向下一个节点，又指向前一个节点，方便双向遍历。
• 循环链表：链表的最后一个节点指向头节点，形成环。

链表的最大特点是可以通过指针动态扩展，解决了数组大小固定的问题，但在随机访问上表现较差，访问某个特定节点需要从头开始遍历。

单向链表的基本实现

class ListNode {
    value: number;
    next: ListNode | null = null;

    constructor(value: number) {
        this.value = value;
    }
}

class LinkedList {
    head: ListNode | null = null;

    // 向链表尾部添加节点
    append(value: number) {
        const newNode = new ListNode(value);
        if (!this.head) {
            this.head = newNode;
            return;
        }
        let current = this.head;
        while (current.next) {
            current = current.next;
        }
        current.next = newNode;
    }

    // 打印链表
    print() {
        let current = this.head;
        const result: number[] = [];
        while (current) {
            result.push(current.value);
            current = current.next;
        }
        console.log(result.join(" -> "));
    }
}

双向链表的基本实现

双向链表比单向链表增加了一个 prev 指针，用于指向前一个节点，适用于需要频繁在两个方向遍历的场景。

class DoubleListNode {
    value: number;
    next: DoubleListNode | null = null;
    prev: DoubleListNode | null = null;

    constructor(value: number) {
        this.value = value;
    }
}

双指针技巧

双指针是一种常用的算法技巧，尤其适合处理数组或链表问题。双指针的基本思想是同时使用两个指针，从不同的起始点出发，通过同步或不同步地移动，达到特定的目标。这一技巧广泛应用于查找、排序、滑动窗口等问题中。

常见的双指针应用场景

1. 快慢指针：一个指针以较快的速度移动，另一个以较慢的速度移动，常用于检测链表中的环或寻找链表的中间节点。
2. 左右指针：两个指针分别从数组或链表的两端出发，逐步向中间移动，常用于寻找对称结构或实现二分查找。
3. 滑动窗口：双指针维护一个窗口，右指针不断扩展窗口，左指针根据需求缩小窗口，常用于字符串或数组的子集问题。

经典问题解析

问题 1：链表中环的检测

在一个单向链表中，可能存在环，即链表的某个节点指向了之前的节点。快慢指针技术可以高效地检测链表中是否存在环。快指针每次移动两步，慢指针每次移动一步，如果链表中存在环，两个指针终会相遇；如果不存在环，快指针会到达链表末端。

代码实现

function hasCycle(head: ListNode | null): boolean {
    if (!head || !head.next) return false;

    let slow = head;
    let fast = head.next;

    while (fast && fast.next) {
        if (slow === fast) return true;
        slow = slow.next!;
        fast = fast.next.next!;
    }

    return false;
}

问题 2：寻找链表的中间节点

使用快慢指针可以快速找到链表的中间节点。慢指针每次移动一步，快指针每次移动两步。当快指针到达链表末尾时，慢指针正好处于链表中间。

代码实现

function findMiddleNode(head: ListNode | null): ListNode | null {
    let slow = head;
    let fast = head;

    while (fast && fast.next) {
        slow = slow.next!;
        fast = fast.next.next!;
    }

    return slow;
}

问题 3：反转链表

链表反转问题是链表操作中的经典问题。我们可以通过双指针遍历链表，逐步反转指针指向，直到整个链表完全反转。

代码实现

function reverseList(head: ListNode | null): ListNode | null {
    let prev: ListNode | null = null;
    let current = head;

    while (current) {
        let nextNode = current.next;
        current.next = prev;
        prev = current;
        current = nextNode;
    }

    return prev;
}

问题 4：链表中倒数第 k 个节点

通过使用快慢指针，快指针先移动 k 步，接着快慢指针同步移动，直到快指针到达链表末尾时，慢指针所指的就是倒数第 k 个节点。

代码实现

function findKthFromEnd(head: ListNode | null, k: number): ListNode | null {
    let slow = head;
    let fast = head;

    // 快指针先走 k 步
    for (let i = 0; i < k; i++) {
        if (!fast) return null; // k 超出链表长度
        fast = fast.next!;
    }

    // 快慢指针一起移动
    while (fast) {
        slow = slow.next!;
        fast = fast.next!;
    }

    return slow;
}

双指针技术通过同时操作两个指针，提高了链表和数组问题的解题效率。快慢指针特别适合用于链表中的环检测和中间节点查找，而左右指针在处理排序数组或对称结构时表现尤为优越。双指针不仅仅是用于链表，还能扩展到数组、字符串等其他数据结构中。