php实现链表操作

PHP实现链表基础结构

链表由节点（Node）构成，每个节点包含数据域和指向下一个节点的指针。以下是单向链表的节点类实现：

class ListNode {
    public $data;
    public $next;

    public function __construct($data) {
        $this->data = $data;
        $this->next = null;
    }
}

链表类封装

创建链表类实现基本操作，初始化时包含头节点指针：

class LinkedList {
    private $head;

    public function __construct() {
        $this->head = null;
    }
}

插入节点操作

头部插入法时间复杂度为O(1)：

public function insertAtBeginning($data) {
    $newNode = new ListNode($data);
    $newNode->next = $this->head;
    $this->head = $newNode;
}

尾部插入需要遍历链表，时间复杂度O(n)：

public function insertAtEnd($data) {
    $newNode = new ListNode($data);

    if ($this->head === null) {
        $this->head = $newNode;
        return;
    }

    $current = $this->head;
    while ($current->next !== null) {
        $current = $current->next;
    }
    $current->next = $newNode;
}

删除节点操作

根据值删除节点需要处理头节点特殊情况：

public function deleteNode($key) {
    if ($this->head === null) return;

    // 处理头节点删除
    if ($this->head->data === $key) {
        $this->head = $this->head->next;
        return;
    }

    $current = $this->head;
    while ($current->next !== null && $current->next->data !== $key) {
        $current = $current->next;
    }

    if ($current->next !== null) {
        $current->next = $current->next->next;
    }
}

查找与遍历

线性查找实现：

public function search($key) {
    $current = $this->head;
    while ($current !== null) {
        if ($current->data === $key) {
            return true;
        }
        $current = $current->next;
    }
    return false;
}

打印链表内容：

public function display() {
    $current = $this->head;
    while ($current !== null) {
        echo $current->data . " -> ";
        $current = $current->next;
    }
    echo "NULL\n";
}

双向链表实现

双向链表节点增加prev指针：

class DoublyListNode {
    public $data;
    public $next;
    public $prev;

    public function __construct($data) {
        $this->data = $data;
        $this->next = null;
        $this->prev = null;
    }
}

双向链表插入需要维护前后节点指针：

public function insertAfter($prevNode, $data) {
    if ($prevNode === null) return;

    $newNode = new DoublyListNode($data);
    $newNode->next = $prevNode->next;
    $prevNode->next = $newNode;
    $newNode->prev = $prevNode;

    if ($newNode->next !== null) {
        $newNode->next->prev = $newNode;
    }
}

环形链表检测

使用快慢指针判断环形链表：

public function hasCycle() {
    if ($this->head === null) return false;

    $slow = $this->head;
    $fast = $this->head->next;

    while ($fast !== null && $fast->next !== null) {
        if ($slow === $fast) return true;
        $slow = $slow->next;
        $fast = $fast->next->next;
    }
    return false;
}

链表反转操作

迭代法反转链表：

public function reverse() {
    $prev = null;
    $current = $this->head;

    while ($current !== null) {
        $next = $current->next;
        $current->next = $prev;
        $prev = $current;
        $current = $next;
    }

    $this->head = $prev;
}

链表排序实现

归并排序适合链表排序：

public function sortList($head) {
    if ($head === null || $head->next === null) {
        return $head;
    }

    // 快慢指针找中点
    $slow = $head;
    $fast = $head->next;
    while ($fast !== null && $fast->next !== null) {
        $slow = $slow->next;
        $fast = $fast->next->next;
    }

    $mid = $slow->next;
    $slow->next = null;

    $left = $this->sortList($head);
    $right = $this->sortList($mid);

    return $this->merge($left, $right);
}

private function merge($left, $right) {
    $dummy = new ListNode(0);
    $current = $dummy;

    while ($left !== null && $right !== null) {
        if ($left->data < $right->data) {
            $current->next = $left;
            $left = $left->next;
        } else {
            $current->next = $right;
            $right = $right->next;
        }
        $current = $current->next;
    }

    $current->next = ($left !== null) ? $left : $right;

    return $dummy->next;
}