一、链表结构基础认知

链表是一种常见的线性数据结构，与数组不同，它不需要连续的内存空间，而是通过节点之间的指针（引用）建立连接。这种特性让链表在插入和删除操作上具有天然优势，时间复杂度可达 O (1)，但随机访问性能较差，需要 O (n) 时间。

在 PHP 中，我们可以通过对象和引用实现链表结构。一个基本的链表由节点组成，每个节点包含数据域和指针域：

• 数据域：存储节点的值
• 指针域：指向链表中的下一个节点（单链表）或同时指向前后节点（双链表）

二、单链表的 PHP 实现

首先我们实现一个基础的单链表结构，包含节点类和链表操作类：

<?php
/**
 * 链表节点类
 */
class ListNode {
    public $val;      // 节点值
    public $next;     // 指向下一个节点的引用
    
    /**
     * 构造函数
     * @param mixed $val 节点值
     */
    public function __construct($val) {
        $this->val = $val;
        $this->next = null;
    }
}

/**
 * 单链表类
 */
class SinglyLinkedList {
    public $head;     // 头节点
    
    /**
     * 构造函数
     */
    public function __construct() {
        $this->head = null;
    }
    
    /**
     * 在链表尾部插入新节点
     * @param mixed $val 节点值
     */
    public function append($val) {
        $newNode = new ListNode($val);
        
        // 链表为空时，新节点作为头节点
        if ($this->head === null) {
            $this->head = $newNode;
            return;
        }
        
        // 遍历到链表尾部
        $current = $this->head;
        while ($current->next !== null) {
            $current = $current->next;
        }
        
        // 在尾部插入新节点
        $current->next = $newNode;
    }
    
    /**
     * 遍历链表并返回所有节点值
     * @return array 节点值数组
     */
    public function traverse() {
        $result = [];
        $current = $this->head;
        
        while ($current !== null) {
            $result[] = $current->val;
            $current = $current->next;
        }
        
        return $result;
    }
}

// 示例用法
$linkedList = new SinglyLinkedList();
$linkedList->append(1);
$linkedList->append(2);
$linkedList->append(3);
print_r($linkedList->traverse()); // 输出: Array ( [0] => 1 [1] => 2 [2] => 3 )
?>

三、链表五大经典应用及实现

1. 链表反转

问题描述：将单链表的所有节点反转，例如将 1->2->3->null 反转为 3->2->1->null。

实现思路：使用三个指针（prev、current、next）遍历链表，逐个反转节点的指向。

<?php
/**
 * 反转单链表
 * @param ListNode $head 链表头节点
 * @return ListNode 反转后的头节点
 */
function reverseList($head) {
    $prev = null;       // 前一个节点
    $current = $head;   // 当前节点
    
    while ($current !== null) {
        $next = $current->next;  // 保存下一个节点
        $current->next = $prev;  // 反转当前节点的指向
        $prev = $current;        // 移动prev指针
        $current = $next;        // 移动current指针
    }
    
    return $prev;  // 反转后prev成为新的头节点
}

// 测试代码
$linkedList = new SinglyLinkedList();
$linkedList->append(1);
$linkedList->append(2);
$linkedList->append(3);
echo "反转前: " . implode('->', $linkedList->traverse()) . "\n";

$linkedList->head = reverseList($linkedList->head);
echo "反转后: " . implode('->', $linkedList->traverse()) . "\n";
?>

复杂度分析：

• 时间复杂度：O (n)，只需遍历一次链表
• 空间复杂度：O (1)，只使用了常数级别的额外空间

2. 检测链表中的环

问题描述：判断一个链表是否存在环结构（即某个节点的 next 指向之前的节点）。

实现思路：使用快慢指针法（Floyd 判圈算法），快指针每次走两步，慢指针每次走一步，如果存在环，两个指针终将相遇。

<?php
/**
 * 检测链表是否有环
 * @param ListNode $head 链表头节点
 * @return bool 是否有环
 */
function hasCycle($head) {
    if ($head === null || $head->next === null) {
        return false; // 空链表或只有一个节点，不可能有环
    }
    
    $slow = $head;       // 慢指针
    $fast = $head->next; // 快指针
    
    while ($slow !== $fast) {
        // 快指针到达尾部，无环
        if ($fast === null || $fast->next === null) {
            return false;
        }
        
        $slow = $slow->next;      // 慢指针走一步
        $fast = $fast->next->next; // 快指针走两步
    }
    
    return true; // 快慢指针相遇，有环
}

// 测试代码
$node1 = new ListNode(1);
$node2 = new ListNode(2);
$node3 = new ListNode(3);
$node1->next = $node2;
$node2->next = $node3;
$node3->next = $node2; // 创建环: 3->2->3...

$linkedList = new SinglyLinkedList();
$linkedList->head = $node1;
var_dump(hasCycle($linkedList->head)); // 输出: bool(true)
?>

复杂度分析：

• 时间复杂度：O (n)，n 为链表长度
• 空间复杂度：O (1)，只使用了两个指针

3. 合并两个有序链表

问题描述：将两个升序排列的链表合并为一个新的升序链表。

实现思路：使用递归或迭代的方式，比较两个链表的当前节点，选择较小的节点加入结果链表。

<?php
/**
 * 合并两个有序链表
 * @param ListNode $l1 第一个有序链表
 * @param ListNode $l2 第二个有序链表
 * @return ListNode 合并后的有序链表
 */
function mergeTwoLists($l1, $l2) {
    // 递归终止条件
    if ($l1 === null) return $l2;
    if ($l2 === null) return $l1;
    
    // 选择较小的节点作为当前节点
    if ($l1->val <= $l2->val) {
        $l1->next = mergeTwoLists($l1->next, $l2);
        return $l1;
    } else {
        $l2->next = mergeTwoLists($l1, $l2->next);
        return $l2;
    }
}

// 测试代码
$list1 = new SinglyLinkedList();
$list1->append(1);
$list1->append(3);
$list1->append(5);

$list2 = new SinglyLinkedList();
$list2->append(2);
$list2->append(4);
$list2->append(6);

$mergedHead = mergeTwoLists($list1->head, $list2->head);
$mergedList = new SinglyLinkedList();
$mergedList->head = $mergedHead;
echo "合并后: " . implode('->', $mergedList->traverse()) . "\n"; // 1->2->3->4->5->6
?>

复杂度分析：

• 时间复杂度：O (m + n)，m 和 n 分别为两个链表的长度
• 空间复杂度：O (m + n)，递归调用栈的深度

4. 找到链表的中间节点

问题描述：找到单链表的中间节点，如果有两个中间节点，返回第二个中间节点。

实现思路：使用快慢指针法，快指针每次走两步，慢指针每次走一步，当快指针到达尾部时，慢指针正好在中间位置。

<?php
/**
 * 找到链表的中间节点
 * @param ListNode $head 链表头节点
 * @return ListNode 中间节点
 */
function middleNode($head) {
    $slow = $head;
    $fast = $head;
    
    // 快指针每次走两步，慢指针每次走一步
    while ($fast !== null && $fast->next !== null) {
        $slow = $slow->next;
        $fast = $fast->next->next;
    }
    
    return $slow;
}

// 测试代码
$linkedList = new SinglyLinkedList();
$linkedList->append(1);
$linkedList->append(2);
$linkedList->append(3);
$linkedList->append(4);
$linkedList->append(5);

$middle = middleNode($linkedList->head);
echo "中间节点值: " . $middle->val . "\n"; // 输出: 3
?>

复杂度分析：

• 时间复杂度：O (n)，只需遍历一次链表
• 空间复杂度：O (1)，只使用了两个指针

5. 删除链表的倒数第 n 个节点

问题描述：删除单链表中倒数第 n 个节点，并返回链表的头节点。

实现思路：使用双指针法，第一个指针先走 n 步，然后两个指针同时前进，当第一个指针到达尾部时，第二个指针正好指向要删除节点的前一个节点。

<?php
/**
 * 删除链表的倒数第n个节点
 * @param ListNode $head 链表头节点
 * @param int $n 倒数第n个节点
 * @return ListNode 处理后的链表头节点
 */
function removeNthFromEnd($head, $n) {
    // 创建哑节点，简化边界处理
    $dummy = new ListNode(0);
    $dummy->next = $head;
    
    $first = $dummy;
    $second = $dummy;
    
    // 第一个指针先走n+1步
    for ($i = 0; $i <= $n; $i++) {
        $first = $first->next;
    }
    
    // 两个指针同时前进
    while ($first !== null) {
        $first = $first->next;
        $second = $second->next;
    }
    
    // 删除倒数第n个节点
    $second->next = $second->next->next;
    
    return $dummy->next;
}

// 测试代码
$linkedList = new SinglyLinkedList();
$linkedList->append(1);
$linkedList->append(2);
$linkedList->append(3);
$linkedList->append(4);
$linkedList->append(5);

$linkedList->head = removeNthFromEnd($linkedList->head, 2);
echo "删除后: " . implode('->', $linkedList->traverse()) . "\n"; // 1->2->3->5
?>

复杂度分析：

• 时间复杂度：O (n)，只需遍历一次链表
• 空间复杂度：O (1)，只使用了常数级别的额外空间

四、链表应用场景总结

链表作为一种灵活的数据结构，在实际开发中有广泛应用：

1. 动态数据存储：适用于元素数量不固定，需要频繁插入删除的场景
2. 实现高级数据结构：如栈、队列、哈希表的链式地址法等
3. 内存管理：操作系统中的内存分配常采用链表结构
4. LRU 缓存：基于双向链表实现最近最少使用缓存淘汰策略
5. 大数据处理：当数据量超过内存限制时，链表的分段存储特性更具优势

掌握链表的操作和经典算法，不仅能提高代码效率，更是理解复杂数据结构和算法思想的基础。在实际开发中，应根据具体场景选择合适的数据结构，平衡时间和空间复杂度。

通过本文的实现示例，希望能帮助读者深入理解链表的工作原理和应用技巧，为更复杂的算法学习打下基础。