php 链表实现

PHP 链表实现方法

链表是一种常见的数据结构，由节点组成，每个节点包含数据和指向下一个节点的指针。以下是几种PHP实现链表的方法。

基础链表实现

定义节点类，包含数据和指向下一个节点的指针：

class ListNode {
    public $data;
    public $next;

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

创建链表并添加节点：

$head = new ListNode(1);
$second = new ListNode(2);
$third = new ListNode(3);

$head->next = $second;
$second->next = $third;

链表操作封装

将链表操作封装成类，便于管理：

class LinkedList {
    private $head;

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

    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 display() {
        $current = $this->head;
        while ($current !== null) {
            echo $current->data . " ";
            $current = $current->next;
        }
    }
}

$list = new LinkedList();
$list->insertAtEnd(10);
$list->insertAtEnd(20);
$list->display(); // 输出: 10 20

双向链表实现

双向链表节点包含指向前一个和后一个节点的指针：

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

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

class DoublyLinkedList {
    private $head;

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

    public function insertAtEnd($data) {
        $newNode = new DoublyListNode($data);
        if ($this->head === null) {
            $this->head = $newNode;
            return;
        }
        $current = $this->head;
        while ($current->next !== null) {
            $current = $current->next;
        }
        $current->next = $newNode;
        $newNode->prev = $current;
    }
}

链表反转

实现链表反转功能：

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;
}

这些方法涵盖了链表的基本操作和常见算法，可以根据需求选择适合的实现方式。