PHP实现单链表翻转操作示例

1. 什么是单链表

单链表是一种常见的数据结构，由一系列节点组成，每个节点包含一个数据元素和一个指向下一个节点的指针。链表的第一个节点称为头节点，最后一个节点的指针指向NULL。节点之间按照其在链表中的顺序相互连接，而不是像数组那样在内存中连续存储。

2. 单链表翻转操作示例

2.1 原始链表示例

假设我们有一个包含5个节点的单链表，节点的值分别为1、2、3、4、5，链表的结构如下：

class ListNode {
    public $val;
    public $next;
    
    public function __construct($val = 0, $next = null) {
        $this->val = $val;
        $this->next = $next;
    }
}
// 创建链表
$head = new ListNode(1);
$node2 = new ListNode(2);
$node3 = new ListNode(3);
$node4 = new ListNode(4);
$node5 = new ListNode(5);
$head->next = $node2;
$node2->next = $node3;
$node3->next = $node4;
$node4->next = $node5;

该链表的结构如图所示：

2.2 实现翻转操作

我们需要实现一个函数，将原始链表翻转，并返回新的头节点。以下是使用PHP实现的翻转操作示例：

function reverseList($head) {
    $prev = null;
    $curr = $head;
    
    while ($curr) {
        $next = $curr->next;
        $curr->next = $prev;
        
        $prev = $curr;
        $curr = $next;
    }
    
    return $prev;
}
// 调用翻转函数
$reversedHead = reverseList($head);

上述代码中，我们使用了三个指针来实现翻转操作。$prev指针用于保存当前节点的前一个节点，$curr指针用于保存当前节点，$next指针用于保存当前节点的下一个节点。每次迭代，我们将$curr的next指针指向$prev，然后将$prev和$curr都向前移动一位。

2.3 翻转后的链表示例

经过翻转操作后，原始链表变为新的链表，节点的值分别为5、4、3、2、1，链表的结构如下：

// 遍历打印链表
function printList($head) {
    $curr = $head;
    
    while ($curr) {
        echo $curr->val . " ";
        $curr = $curr->next;
    }
}
printList($reversedHead); // 输出：5 4 3 2 1

3. 总结

通过以上示例，我们演示了如何使用PHP实现单链表翻转操作。单链表翻转是一种常见的链表操作，可以在某些问题中起到重要的作用。通过调整指针的指向，我们可以改变链表节点之间的连接关系，从而实现翻转操作。

在实际应用中，我们可以根据具体需求对链表进行相应的操作，如插入节点、删除节点等。单链表作为一种灵活的数据结构，可以被广泛应用于各种算法和程序设计中。