php实现链表操作

PHP实现链表操作

链表是一种常见的数据结构，通过节点和指针实现动态内存分配。PHP中可以通过类和对象模拟链表操作。

定义链表节点类

链表的基础是节点，每个节点包含数据和指向下一个节点的指针。

class ListNode {
    public $data;
    public $next;

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

创建链表

实例化节点对象并连接它们形成链表。

$node1 = new ListNode(1);
$node2 = new ListNode(2);
$node3 = new ListNode(3);

$node1->next = $node2;
$node2->next = $node3;

遍历链表

使用循环访问链表中的每个节点。

function traverseLinkedList($head) {
    $current = $head;
    while ($current != null) {
        echo $current->data . " ";
        $current = $current->next;
    }
}

插入节点

在链表指定位置插入新节点。

function insertNode(&$head, $data, $position) {
    $newNode = new ListNode($data);

    if ($position == 0) {
        $newNode->next = $head;
        $head = $newNode;
        return;
    }

    $current = $head;
    for ($i = 0; $i < $position - 1 && $current != null; $i++) {
        $current = $current->next;
    }

    if ($current == null) return;

    $newNode->next = $current->next;
    $current->next = $newNode;
}

删除节点

从链表中移除指定位置的节点。

function deleteNode(&$head, $position) {
    if ($head == null) return;

    if ($position == 0) {
        $head = $head->next;
        return;
    }

    $current = $head;
    for ($i = 0; $i < $position - 1 && $current != null; $i++) {
        $current = $current->next;
    }

    if ($current == null || $current->next == null) return;

    $current->next = $current->next->next;
}

反转链表

改变链表节点指针方向实现反转。

function reverseLinkedList(&$head) {
    $prev = null;
    $current = $head;

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

    $head = $prev;
}

检测环

判断链表是否有环结构。

function hasCycle($head) {
    if ($head == null) return false;

    $slow = $head;
    $fast = $head;

    while ($fast != null && $fast->next != null) {
        $slow = $slow->next;
        $fast = $fast->next->next;

        if ($slow === $fast) {
            return true;
        }
    }

    return false;
}

合并两个有序链表

将两个已排序链表合并为一个新链表。

function mergeTwoLists($l1, $l2) {
    $dummy = new ListNode(0);
    $current = $dummy;

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

    $current->next = ($l1 != null) ? $l1 : $l2;

    return $dummy->next;
}

以上代码实现了链表的基本操作，包括创建、遍历、插入、删除、反转、检测环和合并等功能。可以根据实际需求调整或扩展这些方法。