《剑指Offer》-24.反转链表

题干

定义一个函数，输入一个链表的图节点，反转该链表并输出反转后链表的头节点。链表节点定义如下：

class ListNode {
    int val;
    ListNode next;
}

解题思路

为了防止节点反转的过程中出现链表断裂的情况出现，需要使用一个指针记录节点的下一个节点

为了完成当前节点的反转，还需要记录节点的上一个节点

因此需要三个指针来完成一个节点的反转，对链表的所有节点进行这样的操作就完成了链表的反转

代码实现

<?php

class ListNode
{
    private $val;
    private $next;

    public function __set($name, $value)
    {
        $this->$name = $value;
    }

    public function __get($name)
    {
        return $this->$name;
    }
}

$node1 = new ListNode();
$node1->val = 1;
$node2 = new ListNode();
$node2->val = 2;
$node1->next = $node2;
$node3 = new ListNode();
$node3->val = 3;
$node2->next = $node3;
$node4 = new ListNode();
$node4->val = 4;
$node3->next = $node4;
$node5 = new ListNode();
$node5->val = 5;
$node4->next = $node5;


function reverseList($head)
{
    $prev = null;
    $node = $head;
    $reverseHead = null;
    while (!empty($node)) {
        $next = $node->next;
        if (empty($next)) {
            $reverseHead = $node;
        }

        $node->next = $prev;
        $prev = $node;
        $node = $next;
    }

    return $reverseHead;
}

var_dump(reverseList(null));
var_dump(reverseList($node1));
var_dump(reverseList($node5));